试图了解插入排序算法算法
我读了一些书上的Python，数据结构，并分析和算法设计。我想真正了解中的进出的编码，并成为一个高效的程序员。这是很难要求书澄清，在计算器所以我的问题。我真的发现算法和递归挑战......我贴一些code（插入排序）低于我想明白到底发生了什么。我明白了，一般情况下，应该怎么发生的，但我没有真正得到如何以及为什么。
这是试图分析对Python的空闲的code片，我知道：
键（持有变量）= 8，2，4，9，3，6
和
的 I（保持长度）= 7（1，2，3，4，5，6，7）
我不知道为什么1时在第一行：范围（1，LEN（mylist中））。任何帮助是AP preciated。
mylist中= 8，2，4，9，3，6]
对于j的范围（1，LEN（mylist中））：
键= mylist中[J]。
我= j的
而I＆GT; 0和mylist中[I-1]≥键：
mylist中[i] = mylist中[我 - 1]
我 - = 1
mylist中[i] =键
解决方案
让我尝试打破下来。
首先考虑的列表。这是几乎排序。也就是说，最初的几个因素进行排序，但最后一个元素进行排序。所以它看起来是这样的：
[10，20，30，50，15]
显然，15是放错了地方。那么，如何才能将它？
键= mylist中[4]
mylist中[4] = mylist中[3]
mylist中[3] =键
这将切换周围的15和50所以现在的名单如下：
[10，20，30，15，50]
但是，我们希望在一个循环做几次。要做到这一点，我们可以做的：
，而???：
键= mylist中[I]
mylist中[I] = mylist中[I-1]
mylist中[I-1] =键
我 - = 1
这是循环将回到一个位置的时间交换的两个元素。这会在每次将出顺序位置一个地方回来。但是我们怎么知道什么时候停止？
让我们再看看我们的列表和移动我们要：
[10，20，30，50，15]
[10，20，30，15，50]
[10，20，15，30，50]
[10，15，20，30，50]
＃ 停止！我们现在进行排序！
但所不同的是，上一次在吗？我们移动头号地方回每一次，这是因为15是小于左侧的元件，这意味着其不排序。当这不再是真实的，我们应该停止移动。但是，我们可以很容易地与处理：
键= mylist中[I]
而关键的＆LT; mylist中[I-1]：
mylist中[I] = mylist中[I-1]
mylist中[I-1] =键
我 - = 1
好了，但如果发生了，我们现在试试这个列表进行排序：
[10，20，1] [10，1，20] [1，10，20] ＃ERROR !!
在这一点上有坏事发生。我们尝试检查是否钥匙＆LT; mylist中[I-1]但是，当我们已经达到年初，I = 0，而这个检查列表的末尾。但是，我们应该停止移动，以留在这一点上...
如果我们到达列表的开头，我们不能把我们的枢轴/键进一步，所以我们应该停止。我们更新我们的while循环来处理：
键= mylist中[I]
而I＆GT; 0和关键＆LT; mylist中[I-1]：
mylist中[I] = mylist中[I-1]
mylist中[I-1] =键
我 - = 1
所以，现在我们有一个排序几乎排序列表的技术。但如何才能用它来排序整个名单？我们在时间排序列表的一部分。
[8，2，4，9，3，6]
首先，我们排序的第1个元素：
[8，2，4，9，3，6]
然后我们排序的第2个元素：
[2，8，4，9，3，6]
然后我们前3个元素进行排序
的 [2，4，8，9，3，6]
于是就等等
的 [2，4，8，9，3，6]
[2，4，8，9，3，6]
[2，3，4，8，9，6]
[2，3，4，6，8，9]
不过，我们怎么办，我们这样做吗？随着循环
对于j的范围（LEN（mylist中））：
我= j的
键= mylist中[I]
而I＆GT; 0和关键＆LT; mylist中[I-1]：
mylist中[I] = mylist中[I-1]
mylist中[I-1] =键
我 - = 1
但是我们可以通过跳过第一时间，因为一个元素的列表，显然已排序
对于j的范围（1，LEN（mylist中））：
我= j的
键= mylist中[I]
而I＆GT; 0和关键＆LT; mylist中[I-1]：
mylist中[I] = mylist中[I-1]
mylist中[I-1] =键
我 - = 1
这是一些小的变化，这是没有区别的把我们带回到你原来的code
对于j的范围（1，LEN（mylist中））：
键= mylist中[J]。
我= j的
而I＆GT; 0和关键＆LT; mylist中[I-1]：
mylist中[I] = mylist中[I-1]
我 - = 1
mylist中[i] =键
I'm reading some books on Python, data structures, and analysis and design of algorithms. I want to really understand the in's and out's of coding, and become an efficient programmer. It's difficult to ask the book to clarify, hence my question on stackoverflow. I'm really finding Algorithms and recursion challenging ... I posted some code (insertion sort) below that I'm trying to understand exactly what's happening. I understand, generally, what is supposed to happen, but I'm not really getting the how and why.
From trying to analyze pieces of the code on Python Idle, I know that:
key (holds variables) = 8, 2, 4, 9, 3, 6
and that:
i (holds the length) = 7 ( 1, 2, 3, 4, 5, 6, 7)
I don't know why 1 is used in the first line: range(1, len(mylist)). Any help is appreciated.
mylist = [8, 2, 4, 9, 3, 6]
for j in range(1,len(mylist)):
key = mylist[j]
i = j
while i > 0 and mylist[i-1] > key:
mylist[i] = mylist[i - 1]
i -= 1
mylist[i] = key
解决方案
Let me try to break this down.
Start by considering a list. It is "almost" sorted. That is, the first few elements are sorted, but the last element is not sorted. So it looks something like this:
[10, 20, 30, 50, 15]
Obviously, the 15 is in the wrong place. So how do we move it?
key = mylist[4]
mylist[4] = mylist[3]
mylist[3] = key
That'll switch around the 15 and the 50 so now the list looks like:
[10, 20, 30, 15, 50]
But we'd like to do this several times in a loop. To do that we can do:
while ???:
key = mylist[i]
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
That loop will go back one position at a time swapping the two elements. That'll move the out of order position one place back each time. But how do we know when to stop?
Let's look again at our list and the moves we want to make:
[10, 20, 30, 50, 15]
[10, 20, 30, 15, 50]
[10, 20, 15, 30, 50]
[10, 15, 20, 30, 50]
# stop! we are sorted now!
But what is different that last time around? Every time we move the number one place back, it is because the 15 is less then the element on the left, meaning its not sorted. When that is no longer true we should stop moving. But we can easily deal with that:
key = mylist[i]
while key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Ok, but happens if we now try to sort this list:
[10, 20, 1] [10, 1, 20] [1, 10, 20] # ERROR!!
At this point something bad happens. We try to check whether key < mylist[i-1] but when we've reached the beginning, i = 0, and this checks the end of the list. But we should stop moving to left at this point...
If we reach the beginning of the list, we can't move our pivot/key further so we should stop. We update our while loop to handle that:
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
So now we have a technique for sorting an almost sorted list. But how can we use that to sort a whole list? We sort parts of the list at a time.
[8, 2, 4, 9, 3, 6]
First we sort the first 1 elements:
[8, 2, 4, 9, 3, 6]
Then we sort the first 2 elements:
[2, 8, 4, 9, 3, 6]
Then we sort the first 3 elements
[2, 4, 8, 9, 3, 6]
So on and so forth
[2, 4, 8, 9, 3, 6]
[2, 4, 8, 9, 3, 6]
[2, 3, 4, 8, 9, 6]
[2, 3, 4, 6, 8, 9]
But how do we do we do that? With a for loop
for j in range(len(mylist)):
i = j
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
But we can skip the first time through, because a list of one element is obviously already sorted.
for j in range(1, len(mylist)):
i = j
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
A few minor changes which make no difference brings us back to your original code
for j in range(1, len(mylist)):
key = mylist[j]
i = j
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
i -= 1
mylist[i] = key
