算法导论学习101
首先，对于插入排序算法的大致描述为下
输入为: < a1, a2, a3, ... , an >
输出: 输入序列的一个排列< a1', a2', a3', ... , an'>，使得 a1'< a2'< a3', ... , <an'
前提而言，在任何时候，一个固定数组中的数字，之多只有其中的常数个数字是保存在数组之外的
以下均为伪代码
INSERTION-SORT(A)
1 for j <- 2 to length[A]
2 do key = A[j]
3 // Insert A[j] to the sorted sequence A[1...j-1]
4 i <- j-1
5 while i > 0 && A[i] > key
6 do A[i+1] <- A[i]
7 i <- i-1
8 A[i+1] <- key
所有消耗的时间为每一行的cost * times总和
首先而言，对于line 1由于要从一个数组中提取出一个值与它左边的值作对比，比如如下
1 | 2 | 3 | 4 | 5 | 6
这是一个从1到6的数组，如果要开始取数字进行比较，必须从2开始取，一直取到7，显然最后一个数字是6，取到7是因为程序不知道要取到多少，取到7时候，跳出循环，表示结束。但是对于j可能的值就是从2到length[A]，但是程序运行的次数也就是n-1+1=n
对于line 2 将key赋值为将要进行排序的值，仍然对于上面的数组，从2到length[A]，有n-1次，因此执行次数为n-1
对于line 4，目前是将整个数组分为3部分分别为[1...j-1], j, [j+1...n]，第一部分是已经排序的，第二部分是准备进行排序的，第三部分为还未进行排序的，目前就是，正如注释部分说的，将A[j]插入到前面的排序好的数组队列中。目前是将i来表示j-1，总共会执行n-1次，因为必须要从2开始算，否则就是[1...1-1=0]了，因此为n-1次。
对于line 5，首先将j与[1...j-1]部分做比对，如果A[i] > key，也就是说j左边的数值大于它本身，就应该做相应处理，否则不做任何处理，tj为while循环所做的测试次数，所花费时间如下
对于line 6 - 7，如果满足j小于左边的数值就将这两个数值位置对调，也就是A[i+1] <- A[i]这一步，此时A[i+1]可以理解为j，因为j-1=i, i+1=j，将即将排序的牌插入到比他大的后面，然后从这个值的位置开始继续往左边进行对比，整个要计算的数组长度减少1
对于line 6的测试时间，由于测试体，也就是循环条件，要至不满足条件时候才会退出，因此比循环体多运行一次，因此时间如下
line 7花费时间和line 6相同
对于line 8如果不满足line 5的条件，直接将A[i]赋值为key，排序结束，花费时间为n-1
以下为算法的证明：
初始化: 当j=2时候，此时数组A[1...j-1]只包含一个元素A[1]，显然是已经排序好的，这样就证明了循环不变式在循环的第一轮迭代中是成立的。
保持: 从非形式化的证明来看，在外层的for循环中，要讲A[j-1]，A[j-2]，A[j-3]，等向右移动一个位置，直到找到A[j]的位置为止(line 4 to 7)，此时将A[j]的值插入(line 8)
终止: 分析循环结束的情况。对插入排序来说，当j大于n时，也就是j为n+1时候，外层循环结束，此时子数组为[1...n]，包含了所有元素，已经排序结束。
网友评论