正文
5.平均情况
确实，在最坏情况里，选择排序比插入排序快。但是我们还应该考虑平均情况。
最好情况和最坏情况很少发生。现实世界里，最常出现的是平均情况。
这是很有道理的。你设想一个随便洗乱的数组，出现完全升序或完全降序的可能性有多大？最可能出现的情况应该是随机分布。
下面试试在各种场景中测试插入排序。
完全降序的最坏情况之前已经见过，它每一轮都要比较和平移所遇到的值（这两种操作合计N^2 步）。
对于完全升序的最好情况，因为所有值都已在其正确的位置上，所以每一轮只需要一次比较，完全不用平移。
最坏情况是所有数据都要比较和平移；最好情况是每轮一次比较、零次平移；对于平均情况，总的来看，是比较和平移一半的数据。
如果说插入排序的最坏情况需要 N 2 步，那么平均情况就是 N 2 / 2步。尽管最终大 O都会写成 O(N^2 )。
可以看到插入排序的性能在不同场景中差异很大。最坏、平均、最好情况，分别需要 N^2 、
N^2 / 2、N步。
那么哪种算法更好？选择排序还是插入排序？答案是：看情况。对于平均情况（数组里的值随机分布），它们性能相近。如果你确信数组是大致有序的，那么插入排序比较好。如果是大致逆序，则选择排序更快。
6.希尔排序
希尔排序是对插入排序做了简单的优化，却产生了质的飞跃。直接让不太起眼的插入排序比肩闻名算法界的快速排序。我们知道对于插入排序，数据的元素越是接近有序，那么它的效率就越高；对于完全有序的数组，它甚至可以快到O(N)。
那么希尔排序的主要思想是，我们不断地对数组进行预排序，使数组里大的元素尽量到数组的后面，小的元素尽量到数组的前面。
完成对数组的预排序看，我们采取的方法是对数组进行分组，把数组里间隔相同长度的元素划分为一组。例如：
接下来我们对每一组的元素进行排序。
如图所示，第一趟排序，较大的元素已经到了数组的后面了。接下来再次重新分组，再次预排序：
经过第二趟预排序，我们发现数组已经大致接近有序了，那么最后一次，我们取间隔为1分组，其实就是一次普通的插入排序：
至此，数组已经完全有序了。
通过上面的例子不难看出，希尔排序就是对插入排序的简单优化，引入了预排序的概念。
当gap>1时，进行的是预排序（也就是对每一组进行插入排序）；
当gap=1时，进行对整个数组的插入排序。
7.希尔排序的实现
下面使用C语言实现的希尔排序：
void ShellSort(int* a, int n) { int gap = n; //间隔 while (gap > 1) { gap = gap / 3 + 1; //+1是为了使gap最后等于1 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
代码相较于插入排序并没有改变多少，在插入排序的基础上多了一层循环用来控制gap。
此处可以看出，预排序并不是固定的3次或者4次。而是取决于数组元素个数，这么做一是为了方便控制gap，二是预排序越多次，对整体排序而言更有利，所以我们不用吝啬预排序，并不是预排序越多，花费的步数就越多，时间复杂度就越高。
gap = gap / 3 + 1;
除了这样控制gap外，还有一种常用的方法：
gap = gap / 2;
但是根据有人实验得出，第一种方式比第二种方式快一点点，但是差距很细微，所以两者皆可。
8.希尔排序的效率
希尔排序的时间复杂度并不好算，因为每次取gap的值都不同，而且gap取不同值的情况下，每次预排序所面临的数据也不同。希尔排序的时间复杂度计算需要运用到数学知识，而且目前为止我们也没有得到严格的标准答案。有人在大量实验的基础上得出希尔排序的时间复杂度接近O(N^1.3)。
《数据结构(C语言版)》--- 严蔚敏
数据结构-用面相对象方法与C++描述》--- 殷人昆
因为我们的gap取值的方式是按照Knuth的方式取的，所以以我们这种方式实现的希尔排序时间复杂度暂定为O(N^1.25)。
目前仅仅靠时间复杂度的对比，我们也许感受不到什么叫做质的飞跃，那我们就通过一组数据来对比一下二者的差距。
这是一个测试排序算法所用时间的函数：
void TestOP() { srand(time(0)); const int N = 1000000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int j = 0; for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } printf("%d\n", j); int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); //SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); //HeapSort(a4, N); int end4 = clock(); int begin7 = clock(); //BubbleSort(a7, N); int end7 = clock(); int begin5 = clock(); //QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); //MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end7 - begin7); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); }
我们以排序1百万个元素为例，得到以下结果：
很显然两种排序算法已经不在一个数量级了。
9.总结
懂得区分最好、平均、最坏情况，是为当前场景选择最优算法以及给现有算法调优以适应环境变化的关键。记住，虽然为最坏情况做好准备十分重要，但大部分时间我们面对的是平均情况。
