C++深入浅出讲解希尔排序算法的实现

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现

希尔排序

1.基本思想

希尔排序是在直接插入排序基础上的优化，属于非常牛掰的一个排序。

核心思想：

先进行预排序，让数组接近有序；
直接插入排序

预排序

预排序步骤：

分组排，假设gap==3，间隔为gap的为一组，然后分别使用插入排序的思想对这gap组数据进行排序

多组间隔为gap的预排序，gap由大变小，gap越大，大的数可以越快的到后面，小的数可以越快得到前面，gap越大，预排完越不接近有序，gap越小，预排完越接近有序，gap为1时就是直接插入排序

动图演示：

预排序代码：

		for (int i = 0; i = 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }

这是最初的写法，其实这个代码是可以优化的：

//预排序优化 for (int i = 0; i = 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }

2.算法实现

//希尔排序 void ShellSort(int* a, int n) { //一开始初始化gap为n int gap = n; while (gap > 1)//gap大于1都是预排序，gap==1时为直接插入排序 { //为保证gap最终结果为1，可以gap/=2，也可以是gap=gap/3+1; gap /= 2; //预排序优化 for (int i = 0; i = 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }

完整代码：