8.2.1+8.2.2插入排序

插入排序：

每次将一个待排序的记录按其关键字的大小插入到前面已经排好序的子序列中，直到全部记录插入完成。

第一轮：

如下从第2个元素开始，认为第2个元素之前的序列都是已经排好序的，即此时认为第1个元素排好序的，让当前的元素和之前已经排好序的序列的元素依次进行对比，如果之前已经排好序的元素中有多个比38更大的元素，则这些元素都要右移，给38待排序元素腾出位置。目前38之前就1个元素49,49>38，则49后移38插入到49前面

第2轮：

处理65元素，让65和之前已经排好序的49和38依次进行对比，65>49，如果要得到递增序列，则65不用后移。

第3轮：

处理97元素，让97和之前已经排好序的65、49和38依次进行对比，97>65，则97不用后移。

第4轮：

处理76元素，让76和之前已经排好序的97、65、49和38依次进行对比，76<97，97后移，76继续比较76>65，则76插入到97前面65后面位置。

第5轮：

处理13元素，让13和之前已经排好序的97、76、65、49和38依次进行对比，13<97，97后移，13继续比较13<76，76后移，13继续比较13<65，65后移，13继续比较13<49，49后移，13继续比较13<38，38后移，再往前没有别的元素了，所以13插入到38前面0号位置。

 

第6轮：

处理27元素，让13和之前已经排好序的97、76、65、49、38、13依次进行对比，27<97，97后移，27继续比较27<76，76后移，27继续比较27<65，65后移，27继续比较27<49，49后移，27继续比较27<38，38后移，27继续比较27>13，所以27插入到13后面38前面位置。

第7轮：

处理带下划线49元素，让49和之前已经排好序的97、76、65、49、38、27、13依次进行对比，49<97，97后移，49继续比较49<76，76后移，49继续比较49<65，65后移，49继续比较49==49，所以带下划线49插入到不带下划线49后面65前面位置。（视频上是比49大的元素同时右移，注意右移的元素没有==49的元素，这样是为了保证算法的稳定性）

 

代码实现：

 定义int型数组A和n个元素，变量是i当前需要插入到前面已经排好序的序列中的元素，for循环如果A[i]<A[i-1]即当前元素<它前边一个元素，中间变量temp=A[i]=当前元素值，第2层for循环从i的左边第一个位置即j=i-1依次往左检查当前元素前边的元素是否要比当前元素大即A[j]>temp，所有比temp大的元素都要右移即A[j+1]=A[j],每右移一位都会j--，当j<0时第2层for循环停止，因为元素已经右移了腾出了一个位置了，则要把temp元素赋值给j所指的右边的位置即A[j+1]=temp

 

代码实现(带哨兵)：

 在顺序查找提到过哨兵，原理类似。都是数组的第一个位置index=0不存储元素，而作为哨兵，实际元素存储是从index=1开始的。上同，只有for循环中A[i]<A[i-1]即当前元素<它前边一个元素时才需要移动，不同的是会把当前元素值赋值到A[0]位置即A[0]=A[i](之前是用中间变量temp存储当前元素)，第2层for循环上同，如果当前所指元素左边的元素比当前元素大的都要向右移动一位，开始i=2，A[0]=A[2]=38，j=i-1=1,A[j]>A[i]=49>38，则49向右移动一位A[j+1]=A[j]即A[2]=A[1]=49(A[2]最开始是38,38的值已经赋值给A[0]了，49右移后占了38的位置，原49的位置A[1]空了)，j--即j=0，第2轮内层for循环此时A[0]<A[j]不成立即A[0]<A[0]不成立，跳出内层for循环。A[j+1]=A[1]=A[0]=38。加哨兵之前内层for循环：要判断j>0和A[j]>temp即当前元素左边的元素下标合法>0和当前元素>当前元素左边的元素值

加哨兵之后内层for循环：A[j]>A[0]即当前元素>当前元素左边的元素值，只需判断一次

算法效率分析：

空间复杂度：

O(1)。只需定义 一些辅助变量如i和j、temp以及哨兵模式中空出来的A[0]，这些辅助变量所使用的空间和问题规模n无关，都是常数级的，所以空间复杂度是O(1)

时间复杂度：

在进行插入排序时，假设元素个数是n，都是从第2个元素开始依次往后进行处理，每个元素都要进行一次外层for循环，则共需要进行n-1趟外层for循环，每一趟处理都需要关键字比较和移动，时间开销主要来自于比较和移动这两部分，

最好情况：要排序序列本来有序，则每趟处理时只需比较1次关键字(有序的话确实只比较1次就行了)不需移动，n-1趟处理则需要n-1次关键字对比，则最好的时间复杂度是O(n)

最好情况：要排序序列本来逆序，则每趟处理时都需要和之前已经排好序的关键字都进行一次对比且之前已经排好序的关键字都要向右移动一次，如下当处理到最后一个关键字10时，把A[10]移动到A[0]位置，且要和之前已经排好序的关键字都要进行对比且要让这些已经排好序的关键字都后移一位，则把这些所有趟的对比和移动次数加起来基本是n²数量级，则最坏的时间复杂度是O(n²)

平均时间复杂度：视频上说让(最好+最坏)/2得出来是O(n²)

稳定性：稳定

优化-折半插入排序：

 之前：处理某个元素应该插入到已经排好序的元素中的哪个位置时，是顺序的从左往右找一个个比较，再确定当前元素要插入的位置。

现在：处理某个元素应该插入到已经排好序的元素中的哪个位置时，折半查找已经排好序的元素，在进行比较，更快确定当前元素要插入的位置。因为当前元素之前的序列已经排好序了且元素存储方式是顺序存储方式(跟这有啥关系，因为顺序存储能快速定位元素？？？)，则可以使用折半查找

如下处理元素55：

当前元素Index为i=8，用A[0]记录当前位置元素防止被覆盖A[0]=A[8]=55，然后在55前边序列中采用折半查找尝试找到55应该插入的位置。第一轮，low=1，high=7,mid=(1+7)/2=4，4号位50<55，所以55应该插入50右边的区间内，第2轮，则high=7不变，low=mid+1=5，mid=(7+5)/2=6,6号位70>55，所以55应该插入70左边的区间内，第3轮，则low=5不变，high=mid-1=5，mid=(5+5)/2=5,5号位60>55，所以55应该插入60左边的区间内，第4轮，则low=5不变，high=mid-1=4，此时low>high则折半查找停止，此时[low,i-1]即[5,7]范围内的元素都比当前元素大，则该范围内的元素都要右移一位，给55腾出一个位置，最右边的元素占了A[i]的位置，然后A[low]位置被腾出，再把A[0]保存的当前元素复制到腾出的位置A[low]=A[5]=A[0]=55，大概是这样吧。。。。。。。。。

如下处理元素60(开始序列中已经有一个60了)：

当前元素Index为i=9，用A[0]记录当前位置元素防止被覆盖A[0]=A[9]=60，然后在60前边序列中采用折半查找尝试找到60应该插入的位置。第一轮，low=1，high=8,mid=(1+8)/2=4，4号位50<60，所以60应该插入50右边的区间内，第2轮，则high=8不变，low=mid+1=5，mid=(8+5)/2=6,6号位60=60，按照折半查找的逻辑当找到和目标元素相同的关键字时就会停止折半查找，但是为了保证插入排序的稳定性，当发现和当前处理元素值相同的元素时，还应该往当前值相同元素的右边查找来确定插入位置，即要把和已有值相同的新元素插入到后边位置。所以60应该插入60右边的区间内，第3轮，则high=8不变，low=mid+1=7，mid=(7+8)/2=7,7号位70>60，所以60应该插入70左边的区间内，第4轮，则low=7不变，high=mid-1=6，此时low>high则折半查找停止，此时[low,i-1]即[7,8]范围内的元素都比当前元素大，则该范围内的元素都要右移一位，给60腾出一个位置，最右边的元素占了A[i]的位置，然后A[low]位置被腾出，再把A[0]保存的当前元素复制到腾出的位置A[low]=A[7]=A[0]=60，大概是这样吧。。。。。。。。。

 

如下处理元素90(low>i-1情况，不需移动)：

当前元素Index为i=10，用A[0]记录当前位置元素防止被覆盖A[0]=A[10]=90，然后在90前边序列中采用折半查找尝试找到90应该插入的位置。第一轮，low=1，high=9,mid=(1+9)/2=5，5号位55<90，所以90应该插入55右边的区间内，第2轮，则high=9不变，low=mid+1=6，mid=(6+9)/2=7,7号位60<90，所以90应该插入60右边的区间内，第3轮，则high=9不变，low=mid+1=8，mid=(8+9)/2=8,8号位70<90，所以90应该插入70右边的区间内，第4轮，则high=9不变，low=mid+1=9，mid=(9+9)/2=9,9号位80<90，所以90应该插入80右边的区间内，第5轮，则high=9不变，low=mid+1=10，此时low>high则折半查找停止，此时[low,i-1]即[10,9]范围内的元素都比当前元素大，很明显这个区间范围有问题，即low>i-1则此时并不需要移动任何一个元素。大概是这样吧。。。。。。。。。

如下处理元素10(low>i-1情况，不需移动)：

当前元素Index为i=11，用A[0]记录当前位置元素防止被覆盖A[0]=A[11]=10，上同经过一系列处理，high最终停在0号位，low停在1号位，low>high折半查找停止，此时[low,i-1]即[1,10]范围内的元素都比当前元素大，则该范围内的元素都要右移一位，给10腾出一个位置，最右边的元素占了A[i]的位置，然后A[low]位置被腾出，再把A[0]保存的当前元素复制到腾出的位置A[low]=A[1]=A[0]=10。大概是这样吧。。。。。。。。。

王道书里写的是移动[high+1,i-1]范围内的元素，和移动[low,i-1]相同，因为折半查找停止时一定是high在low左边相邻的一个位置，所以high+1=low

优化折半插入排序代码版：

时间复杂度依然是O(n²)

如下截图中的while循环是折半查找的实现，在俩元素相等时走else保证插入排序稳定性让mid+1，内层for循环用于移动[low,i-1]的元素

对链表进行插入排序：

 上边的排序都是基于顺序表(因为是顺序表才可用折半查找)，如果是基于链表则折半查找不能用，对链表进行排序时移动元素位置只需改变元素指针指向即移动次数变少，但是关键字比较次数没变，则只要用插入排序，时间复杂度还是O(n²)

知识回顾：

 

。。。。。。。。。。。。。。。。