这是插入排序的 Python 实现，我尝试遵循纸上的值，但是一旦计数变量 i 大于 len(s)，我不知道该怎么办，它如何/为什么仍然运行？
def sort_numbers(s):
for i in range(1, len(s)):
val = s[i]
j = i - 1
while (j >= 0) and (s[j] > val):
s[j+1] = s[j]
j = j - 1
s[j+1] = val
def main():
x = eval(input("Enter numbers to be sorted: "))
x = list(x)
sort_numbers(x)
print(x)
或者，这个：
def ins_sort(k):
for i in range(1,len(k)): #since we want to swap an item with previous one, we start from 1
j = i #create i's copy (or not)
temp = k[j] #temp will be used for comparison with previous items, and sent to the place it belongs
while j > 0 and temp < k[j-1]: #j>0 bcoz no point going till k[0] since there is no seat available on its left, for temp
k[j] = k[j-1] #Move the bigger item 1 step right to make room for temp
j=j-1 #take k[j] all the way left to the place where it has a smaller/no value to its left.
k[j] = temp
return k
考虑 [3, 2, 1]
循环从 3 开始。因为它是列表中的第一项，所以没有其他事情可做。
[3, 2, 1]
下一个项目是 2。它将 2 与 3 进行比较，由于 2 小于 3，因此交换它们，首先将 3 放在第二个位置，然后将 2 放在第一个位置。
[2, 3, 1]
最后一项是 1。由于 1 小于 3，它移动了 3。
[2, 3, 3]
由于 1 小于 2，因此它交换移动 2。
[2, 2, 3]
然后它在开头插入 1。
[1, 2, 3]
要了解该实现是如何工作的，请在此处查看可视化：http: //goo.gl/piDCnm
但是，这是插入排序的一个不太容易混淆的实现：
def insertion_sort(seq):
for i in range(1, len(seq)):
j = i
while j > 0 and seq[j - 1] > seq[j]:
seq[j - 1], seq[j] = seq[j], seq[j - 1]
j -= 1
递归实现
def insert(x, L):
if [] == L: return [x]
elif x <= L[0]: return [x] + L
else: return [L[0]] + insert(x,L[1:])
def insertion_sort(L):
if [] == L: return []
else: return insert(L[0], insertion_sort(L[1:]))
# test
import random
L = [random.randint(1,50) for _ in range(10)]
print L
print insertion_sort(L)
如果我们考虑从左到右的数组 [LeftMost, ..., RightMost]，插入排序对每个项目执行以下过程：
这是排序算法的关键。一旦你完成了第 i 项的处理，你就有了一个排序数组，从它最初的位置一直到开始（最左边）。
旁注（对于理解算法并不重要，但可能有用）：考虑到这一点，您可以推断出该算法的复杂性（在最坏情况比较中测量）为 O(N^2)，其中 N = len(s)。它类似于有两个嵌套的 for 语句。
这个视频很好地解释了上述内容，你知道他们在说什么，一张图片值 1000 字。
有一些信息有助于理解插入排序。
首先，i永远不要大于len(s)。事实上，它也永远不等于它。所做的是range(1, len(s))产生一个可以迭代的不可变序列。您将在以下语句下拥有什么（让我们假设len(s) = 3）：
for i in range(1, len(s)):
...
是这样的：
for i in (1, 2):
...
您可以验证自己：
>>> list(range(1, 3))
>>> [1, 2]
因此，您将迭代两次，第一次使用i = 1，第二次使用i = 2。
其次，它有助于提醒自己，您正在排序的列表本质上由两部分组成：已排序的部分 ( list[0:i-1]) 和尚未排序的部分 ( [list[i:])。您试图在每次迭代中使用插入排序来实现的是找到一个将当前值放入排序列表的位置。我们很快就会谈到这一点。
第三，该算法可以被认为是完成两个截然不同的任务。第一个是遍历列表中的所有成员并确保列表已排序。这就是外循环关注的部分（当然，内循环参与实际检查，但它有助于简化）。另一种是为列表中的元素找到适当的位置，以便对列表进行排序。即，如果你有一个 list letters = ['a', 'b', 'd', 'c']，如果要按升序对列表进行排序，'c'显然应该去letters[2]并且'd'需要占据's 以前的位置。'c'这就是内部while循环所做的部分。
实际上，while 循环（和s[j+1] = val语句）如何确保列表被排序是非常聪明的。首先，它确保我们没有过度扩张（j >= 0条件）。也就是说，我们没有选择s[-1]元素，在 Python 中它将是列表中的最后一个元素，而其他语言，如 Java，则ArrayIndexOutOfBounds例外。然后，它会问：我持有的数字是否低于之前的数字？如果是这样，这意味着列表没有排序，我们需要将较大的第一个位置移到列表的末尾（如果你愿意的话，向右移动）。请注意，我们用来比较其他元素的元素保持不变。我们将它保存在val变量中。因此，我们不必担心在移动值时通过覆盖它而意外丢失它。
现在，一旦我们将较大的值向右移动，我们就会递减j并再次问同样的问题：at 的值是否s[j]大于我们所拥有的值val？我们继续这样做，直到我们找到低于我们所拥有的价值val，或者我们达到s[0]但没有找到更低的价值。这意味着我们持有的是列表中最小的数字。无论哪种方式，我们都会跳出while循环并用我们拥有的值覆盖s[j+1]，这样我们就不会失去val.
要查看它在实践中的外观，请考虑一个列表：[2, 3, 4, 5, 1]. 假设我们迭代直到达到 number 1，此时我们进入 while 循环，因为5 > 1。采取的步骤是：
2, 3, 4, 5, 1 # val = 1, s[j] = 5, j = 3 5 > 1
2, 3, 4, 5, 5 # val = 1, s[j] = 4, j = 2 4 > 1
2, 3, 4, 4, 5 # val = 1, s[j] = 5, j = 1 3 > 1
2, 3, 3, 4, 5 # val = 1, s[j] = 5, j = 0 2 > 1
2, 2, 3, 4, 5 # val = 1, s[j] = 5, j = -1 break out of while
1, 2, 3, 4, 5 # val = 1, s[j] = 5, j = -1 put val into s[0]
基本上就是这样。遍历循环，检查当前值之前的值是否低于我们所持有的值，如果不是，则将这些值向右移动以为我们的值腾出空间。你有它 - 插入排序。
编辑：如果您仍然很难了解它是如何工作的，那么有一个非常好的代码审查可视化解释。
def insertionsort(list):
for i in range(1,len(list)):
temp=list[i]
j=i-1
while temp<+list[j] and j>=0:
list[j+1]=list[j]
j=j-1
list[j+1]=temp
return list
list=eval(raw_input('Enter a list:'))
print insertionsort(list)
这将对您有所帮助。
试试这个，适用于递增和递减顺序：
import operator
def insertion_sort(arr, reverse=False):
# check if array is empty or not
if arr is None:
raise TypeError("Data cannot be none")
n = len(arr)
# if length of array is less than two it is already sorted
if n < 2:
return arr
lgt = operator.gt if reverse else operator.lt
# Traverse through 1 to len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and lgt(key, arr[j]):
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
li = [1, 4, 8, 9, 42, 0, 36]
print(insertion_sort(li))
python函数从到range(start, end)开始计数。也就是说，永远不会成为价值观的一部分。因此，如果您有，例如，并且是一个包含 10 个整数的数组（在 Python 中是一个列表），则为10，并且将返回，以便您可以索引 A 中的每个元素。startend - 1endrange()range(len(A))Alen(A)range(len(A))(0,1,2,3,4,5,6,7,8,9)
在你的情况下，我永远不会比len(s) - 1.
在纸上遵循您的代码可能很有用，但您必须确保编程语言完全按照您的想法执行，有时实现并不直观。跟踪程序值的一种快速而简单的方法是使用print语句。例如：
def sort_numbers(s):
for i in range(1, len(s)):
# let's see what values i takes on
print "i = ", i
val = s[i]
j = i - 1
while (j >= 0) and (s[j] > val):
s[j+1] = s[j]
j = j - 1
s[j+1] = val
+带有两个 for 循环和描述性名称的替代方案。
def insertionSort(list):
for outerIndex in range(len(list)):
for innerIndex in range(outerIndex, 0, -1):
if list[innerIndex] >= list[innerIndex - 1]:
break
list[innerIndex], list[innerIndex - 1] = list[innerIndex - 1], list[innerIndex]
return list
print insertionSort([3, 1e-10, 7e5, 2.3, 100, -2.5, 12.1])
# => [-2.5, 1e-10, 2.3, 3, 12.1, 100, 700000.0]
通过递归插入排序：
k=1# def insertionsort(a): # should be written before k=1
c=a[:]
def swap(k,c,a):
if c[k-1] > c[k]:
c[k-1] = a[k]
c[k] = a[k-1]
a = c[:]
if max(c[:k])!= c[k-1]:
swap(k-1,c,a)
if k < len(a)-1:
return swap(k + 1, c,a)
return c
return swap(k,c,a)
print(insertionsort(b))
def insertSort(list):
for i in range(0, len(list)):
index = list[i] // index holder for swapAt position
while i > 0 and index < list[i - 1]:
list[i] = list[i - 1]
i = i - 1
list[i] = index
return list
print(insert([3,3,6,1,7,2,8])) -> [1, 2, 3, 3, 6, 7, 8]
对数组进行排序的简单方法。
# Mutate the constant input
# loop into the array
# check if the array[j] have to be greater than 0 and a[j] is less than a[j - 1]
# then swap values and decrease the value swapped.
def insertionSort(array):
a = array
for i in range(0,len(a)):
j = i
while j > 0 and a[j] < a[j - 1]:
a[j], a[j - 1] = a[j - 1], a[j]
j -= 1
return a
# input-> [2,1,3] then array[j] > 0 and array[j] < array[j - 1] -> swap -> decrease j
def insertion(x):
for i in range(1, len(x)):
while x[i - 1] > x[i] and i >= 0:
x[i - 1], x[i] = x[i], x[i - 1]
i -= 1
return x
类似的东西
列表切片和冒泡排序的简单组合
s = [54,26,93,17,77,31,44,55,20]
for i in range(1,len(s)+1):
b = s[0:i]
a = b
count = 0
while count<len(a): # while loop to perform the for loop len(a) number of times-like in bubble sort
for j in range(len(a)-1): # for loop compares every j'th element with next element
if a[j] >= a[j+1-len(a)]:
temp = a[j]
a[j] = a[j+1-len(a)]
a[j+1-len(a)] = temp
count = count+1
print a
def ins(l):
for i in range(1, len(l)):
current_index = i
current_value = l[i]
while current_index > 0 and current_value < l[current_index - 1]:
l[current_index] = l[current_index - 1]
current_index -= 1
l[current_index] = current_value
print(l)
def insertionSort(alist):
for index in range(1, len(alist)):
currentvalue = alist[index]
position = index
while position > 0 and alist[position-1] > currentvalue:
alist[position] = alist[position-1]
print(alist)
position -= 1
alist[position] = currentvalue
alist = [int(i) for i in input().split()]
insertionSort(alist)
__author__ = 'Dharmjit'
def InsertionSort(list):
for index in range(1,len(list)):
curr = list[index]
position = index
while position > 0 and list[position-1] > curr:
list[position] = list[position-1]
position = position - 1
list[position] = curr
return list
l = [2,1,5,3,9,6,7]
print(InsertionSort(l))
[1,2,3,5,6,7,9]
你可以在这里看到整个概念 - http://pythonplanet.blogspot.in/2015/07/sorting-algorithm-1-insertion-sort.html
def sort_numbers(list):
for i in range(1, len(list)):
val = list[i]
j = i - 1
while (j >= 0) and (list[j] > val):
list[j+1] = list[j]
j = j - 1
list[j+1] = val
n = int(input("Enter the no. of elements"))
list = []
for i in range(0,n):
t = int(input())
list.append(t)
sort_numbers(list)
print list
我浏览了许多这些帖子，我认为人们过度复杂化了这个问题。如果我做错了，请纠正我，但这是我对此的解释。
def insert(L): # this creates the definition and assines the list that you input to L
for i in range(len(L)): # this then loops the next code for the length of the list
while i > 0 and L[i] < L[i-1]: # this is the main part of the code where it checks
# if the value from the list is less than the one before it and if it is then it
# swaps them around
L[i-1], L[i] = L[i], L[i-1] # this code just swaps round the values
print (L)# prints the list out at the end of each part
L = [5,2,3,7,6,9,7]
insert(L)
使用它输出：
[2, 5, 3, 7, 6, 9, 7]
[2, 3, 5, 7, 6, 9, 7]
[2, 3, 5, 6, 7, 9, 7]
[2, 3, 5, 6, 7, 7, 9]
print 函数也可以从行中删除，并且可以放在 for 循环之外，以便它只在末尾打印列表。这只会给出最后一行：
[2, 3, 5, 6, 7, 7, 9]
`enter code here`
def insertion_sort(data):
n = len(data)
for i in range(n):
index = i
value = data[i]
while data[index] < data[index-1] and index > 0:
#print("index : " ,index)
data[index] = data[index-1]
data[index-1] = value
#print(f"DATA[index-1] : { data[index-1] } DATA[index] : { data[index] } " )
index -= 1
data[index] = value
return data;
if __name__ == "__main__":
data = []
size = int(input("How many data you want to enter ? : "))
print("\n-----------------INITIALISING----------------")
for i in range(size):
temp = int(input(f"Enter element { i + 1 } : "))
data.append(temp)
print("\n-----------------BEFORE SORTING DATA----------")
print(data)
print("\n-----------------AFTER SORTING DATA-----------")
print(insertion_sort(data))
def insertie(x):
nrc=0
nrm=0
for i in range(0,len(x)):
aux=x[i]
nrm=nrm+1
j=i-1
while j >= 0 and aux < x[j]:
nrc=nrc+1
x[j+1]=x[j]
nrm=nrm+1
j=j-1
nrc=nrc+1
x[j+1]=aux
nrm=nrm+1
return x
x=[7,5,4,9,1,4,0,1]
print insertie(x)