这是第三篇，插入排序算法。 直接插入排序、希尔排序。
简介插入排序是一种简单直观的排序方法，基本思想是将要排序的记录插入到以前按其关键字大小排序的子序列中，直到插入完所有记录。
在基于插入的排序算法中，主要介绍直接插入排序和希尔排序。
一.直接插入排序排序中，假设排序对象表L[1.n]的某个排序中的某个时间点的状态如下。
要将元素L(I )插入到有序子序列l )1.I-1 )中，必须执行以下操作(为了避免混淆，以下用l )表示表格，用l )表示元素)
为了找出L[1.i-1]内的L(I )的插入位置k，将L(K……I-1 )内的所有元素逐个向后移动并将l ) I )复制到l ) k ) l ) 1…n )的排序因为插入排序在实现中通常采用就地排序(空间复杂度o )1)，所以在从后向前比较的过程中，必须重复将已排序的元素逐步向后移动，为新元素提供插入空间。
假设第一个序列是49、38、65、97、76、13、27和49，则前49个可以被视为自己排序的子序列。 排序过程如下图所示。
1.例程
/* * * * * * * * * * * * * * * * * * * * *直接插入排序* * * * * * * * * * * * * * * * * * *直接插入ilength； I )//从编号1到循环if(data[I]data[I-1] ) /如果后面小于前面，则在前面的顺序表中插入较小的一个({temp=data[i] )； //复制到哨兵for (j=I-1； j=0tempdata[j]； j----//从后向前查找要插入的位置data[j 1]=data[j]；//将数据向后偏移[j1]=temp； ///将哨兵复制到插入位置}}intmain () {inti=0； int data [ ]={ 23，64，24，12，9，16，53，57 }； inttemp[]={0}； intlength=sizeof(data )/sizeof (int ) )； insertsort(data，length )； for(I=0； ilength； I ) (printf )、data[i]； }printf((n )； } 2.性能分析
2.1适用性
适用于顺序存储和链式存储的线性表。 大多数排序算法仅适用于顺序存储的线性表。 对于链接存储，可以稍后查找指定元素的位置。
2.2空间复杂度
tyle="margin-left:0pt;"> 仅使用常数个辅助单元，故空间效率为：O(1);2.3时间复杂度
排序过程中，向有序子表中逐个地插入元素的操作进行了 n-1 趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
在最好情况下，表元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)。
在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为 2+3+....+n，总的移动次数也达到最大，为 (2+1)+(3+1)+....+(n+1)。考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 n2/4。
因此直接插入排序算法的时间复杂度为 O(n2)。
2.4稳定性
由于每次插入元素，总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。
二.希尔排序
从前面的分析可知，直接插入排序算法的时间复杂度为 O(n2），但若待排序列为“正序”时， 其时间复杂度可提高至O(n)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。
希尔排序的基本思想是：先将待排序表分割成若干形如L [i, i + d, i + 2d,……, i + kd] 的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的过程如下：先取一个小于n的步长d1 ，把表中的全部记录分成d1组，所有距离为d1 的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长d2<d1，重复上述过程，直到所取到的 d1 = 1，即所有记录己放在同一组中，再进行直接插入排序，由于此时已具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是 d1 = n/2, di+1 = Li/2，并且最后一个增量等于1。
若以表{49, 38, 65, 97, 76, 13, 27, 49, 55, 04}为例，第一趟取增量d1 = 5，将该序列分成5个子序列，分别对各子序列进行直接插入排序；第一趟取增量d2 = 3，分别对3个子序列进行直接插入排序；最后对整个序列进行一趟直接插入排序。整个排序过程如下图所示：
1.例程
/********************************* 希尔排序（插入排序） *********************************/#include <stdio.h>#include <stdlib.h>#include <string.h>int shell_sort(int *data, int length) { int gap = 0; int i = 0, j = 0; int temp; for (gap = length / 2;gap >= 1; gap /= 2) { //每次的步长 = 上一次/2 for (i = gap;i < length;i ++) { //从gap到length每个比较 /* 和插入排序基本一样，只不过插入的gap=1 刚开始 temp=data[6], j=i-gap=0 若 temp<data[0], 则data[j+gap=6]=data[0], j=j-gap=-6, 跳出循环， data[j+gap=0] = temp 若 temp>=data[0],则跳出循环， data[j+gap=6]=temp 即无变换 */ temp = data[i]; for (j = i-gap; j >= 0 && temp < data[j]; j = j - gap) { data[j+gap] = data[j]; } data[j+gap] = temp; } } return 0;}int main() { int i = 0; int data[] = {23, 64, 24, 12, 9, 16, 53, 57}; int temp[] = {0}; int length = sizeof(data) / sizeof(int); shell_sort(data, length); for (i = 0;i < length;i ++) { printf("%4d", data[i]); } printf("n");}2.性能分析
2.1适用性
仅适用于线性表为顺序存储的情况。
2.2空间复杂度
仅使用常数个辅助单元，故空间效率为：O(1);
2.3时间复杂度
由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难，所以时间复杂度分析比较难。当n在某个特定范围时，希尔排序的时间复杂度约为 O(n1.3) ，在最坏情况下希尔排序的时间复杂度为 O(n2)。
2.4稳定性
当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。例如例子中的49和49。
因希尔排序是不稳定的排序方法。
下一篇，第四篇，归并排序算法。
个人公众号：Xtizzzz分享
参考：
《王道数据结构》