Python 插入排序是如何工作的？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12755568/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How does Python insertion sort work?
提问by CT Hildreth
Here's a Python implementation of insertion sort, I tried to follow the values on paper but once the counting variable i gets bigger than len(s) I don't know what to do, how/why does it still run?
这是插入排序的 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)
回答by Nathan Villaescusa
Consider [3, 2, 1]
考虑 [3, 2, 1]
The loop starts with 3. Since it is the first item in the list there is nothing else to do.
循环从 3 开始。由于它是列表中的第一项，因此无需执行其他操作。
[3, 2, 1]
The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position.
下一项是 2。它将 2 与 3 进行比较，由于 2 小于 3，因此将它们交换，首先将 3 放在第二个位置，然后将 2 放在第一个位置。
[2, 3, 1]
The last item is 1. Since 1 is less than 3 it moves 3 over.
最后一项是 1。因为 1 小于 3，所以它移动了 3。
[2, 3, 3]
Since 1 is less than 2 it swaps moves 2 over.
由于 1 小于 2，它交换移动 2。
[2, 2, 3]
Then it inserts 1 at the beginning.
然后它在开头插入 1。
[1, 2, 3]
回答by Damian Schenkelman
If we consider an array from left to right [LeftMost, ..., RightMost], an insertion sort performs the following procedure for each item:
如果我们从左到右考虑一个数组 [LeftMost, ..., RightMost]，插入排序对每个项目执行以下过程：
- Get the current value i.
- Get the value j (where j = i-1 in the first iteration, or basically the first element to the left of i). In the first iteration of the while array[i] and array[j] are to consecutive elements. For example, if array = [... 60, 100, 50, ...], and array[i] is 50, then array[j] is 100.
- If the previous value is greater than the current one, then it swaps the two values. Basically if you had something like [..., 60, 100, 50, ...] before this operation takes place, you will end up with [..., 60, 50, 100, ...]. The idea is that you move each item i left as long as there are elements to the left of it that are lower.
This is the key of the sort algorithm. Once you are done processing at item i, you have a sorted array from where it originally was all the way to the beggining (left most).
- Decrease the value of j by one. and go back to step 1 (In this example, this will lead you to compare 50 and 60 and swap them).
- 获取当前值 i。
- 获取值 j（其中 j = i-1 在第一次迭代中，或者基本上是 i 左侧的第一个元素）。在 while array[i] 和 array[j] 的第一次迭代中，是连续元素。例如，如果 array = [... 60, 100, 50, ...]，并且 array[i] 为 50，则 array[j] 为 100。
- 如果前一个值大于当前值，则交换两个值。基本上，如果在此操作发生之前你有类似 [..., 60, 100, 50, ...] 的东西，你最终会得到 [..., 60, 50, 100, ...]。这个想法是你移动我留下的每个项目，只要它左边的元素较低。
这是排序算法的关键。一旦你完成了第 i 项的处理，你就有了一个排序的数组，从它最初的位置一直到开始（最左边）。
- 将 j 的值减一。并返回到步骤 1（在本例中，这将引导您比较 50 和 60 并交换它们）。
Sidenote (not important to understand the algorithm, but could be useful): With that in mind, you can deduce that this algorithm's complexity (measured in worst case comparisons) is O(N^2) where N = len(s). It is similar to having two nested for statements.
旁注（对于理解算法并不重要，但可能有用）：考虑到这一点，您可以推断出该算法的复杂性（在最坏情况比较中测量）为 O(N^2)，其中 N = len(s)。它类似于有两个嵌套的 for 语句。
This videodoes a great job explaining the above, and you know what they say, an image is worth 1000 words.
该视频很好地解释了上述内容，您知道他们在说什么，一张图片值 1000 字。
回答by Paul Vasiu
The python range(start, end)function starts counting from startto end - 1. That is, endwill never be part of the range()values. So if you have, for example, range(len(A)), and Ais an array (in Python, a list) of 10 integers, len(A)will be 10, and range(len(A))will return (0,1,2,3,4,5,6,7,8,9)so you can index every element in A.
pythonrange(start, end)函数从start到开始计数end - 1。也就是说，end永远不会成为range()值的一部分。因此，例如，如果您有 ,range(len(A))并且A是一个包含 10 个整数的数组（在 Python 中为列表），len(A)则将为 10，并且range(len(A))将返回(0,1,2,3,4,5,6,7,8,9)以便您可以索引 A 中的每个元素。
In your case, i never gets bigger than len(s) - 1.
在您的情况下， i 永远不会大于len(s) - 1.
Following your code on paper can be useful, but you have to make sure that the programming language does exactly what you think it does, and sometimes the implementation isn't intuitive. A fast and simple way of tracing your program values is to use printstatements. For example:
遵循纸上的代码可能很有用，但您必须确保编程语言完全按照您的想法执行，有时实现并不直观。跟踪程序值的一种快速而简单的方法是使用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
回答by Aziz Alto
To see how that implementation works, check it out visualized here: http://goo.gl/piDCnm
要了解该实现的工作原理，请在此处查看可视化：http: //goo.gl/piDCnm
However, here is a less confusing implementation of insertion sort:
但是，这是插入排序的一个不太容易混淆的实现：
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
回答by arpit gupta
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)
This will help you.
这会帮助你。
回答by Aditya
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
回答by Ketan
Or, this one:
或者，这个：
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 #bcoz reducing i directly will mess our for loop, so we reduce its copy j instead
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
回答by Akash
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)
回答by Deepi
__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]
You can see the whole concept here- http://pythonplanet.blogspot.in/2015/07/sorting-algorithm-1-insertion-sort.html
你可以在这里看到整个概念 - http://pythonplanet.blogspot.in/2015/07/sorting-algorithm-1-insertion-sort.html
回答by Arnaldo P. Figueira Figueira
a recursive implementation
递归实现
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)
