2018-08-08 算法导论(2.1 插入排序)

算法导论学习101

---

首先，对于插入排序算法的大致描述为下
输入为: < a₁, a₂, a₃, ... , a_n >
输出: 输入序列的一个排列< a₁^', a₂^', a₃^', ... , a_n^'>，使得 a₁^'< a₂^'< a₃^', ... , <a_n^'

前提而言，在任何时候，一个固定数组中的数字，之多只有其中的常数个数字是保存在数组之外的

以下均为伪代码

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左边的数值大于它本身，就应该做相应处理，否则不做任何处理，t_j为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]，包含了所有元素，已经排序结束。