vlambda博客
学习文章列表

1.算法描述：

    希尔排序是一种高级排序算法，本质上也是一种插入排序，但是对于插入排序来说，每次比较以及交换元素的时候，只能变动一个位置，希尔排序通过设置增量的方式，将多个无序元素进行分组，当增量不为1时，这样可以一次变动多个位置(但是对于分组来说，其实就是插入排序，因为对于分组来说它其实也只是每次移动了分组内的一个位置，不过对于原始数据来说，是一次性移动了多个位置)，随着增量的减小，数据也慢慢变得部分有序，直到增量减小为1时，最后一个排序比较操作，其实就是插入排序，因为此时数据元素已经基本有序，此时的插入排序操作，可以通过比较小的代价就能得到完全有序的结果。

2.思路

1. 设定待排序数组arr。

2. 定义最开始的增量(这里我们使用希尔增量)，增量是希尔排序中希尔给出的增量序列ht = N / 2, h[k+1] = h[k] / 2，即{N/2, (N / 2)/2, ..., 1}，N这里指的是待排序数组的长度，N / 2，只保留整数位。将待排序数组根据增量进行分组(每个元素之间的差距是预设的增量)。增量最后会减少为1(这是必要的)。
   

3. 默认分组的第一个元素是已经有序的，从分组的第二个元素开始执行插入排序操作(与分组中的有序元素进行比较)，如果第二个元素大于比较的元素，则交换他们的位置。

4. .....

5. 直到所有分组的所有待排序元素全部都与已排序部分进行了比较(比较过程中，会发生数据交换操作，每个分组中的有序部分会增加，无序部分会减少)，结束当前排序，
   

6. 重复2345操作，直到数据完全有序。
   

    希尔排序其实也是一种插入排序，不过插入排序每次只能移动一个位置，而对于希尔排序来说，因为根据增量将数据进行了分组，最开始的情况下，增量最大，分组数最多，这时候，每次元素进行比较之后，发现不符合顺序的话，是可以一次性移动多个位置，当然随着增量的减小，每个分组的元素数增多，分组数相应减少，每次比较可以移动的位置也会相应的减少，但是同时因为每次都对分组进行排序，所以随着增量的减小，数据是开始变的部分有序的，所以当增量减小为1的时候，这个时候，待排序的数组中的数据其实是部分有序的，所以这个时候，插入排序的操作，效率是很高的，因为此时数据基本是有序的。

3.举例

要排序数组：[1,9,10,8,-4]

• 设置增量，增量为2，第一次分组（得到A分组[1,10,-4]和B分组[9,8]，排序后数据为[10,9,1,8,-4]）,默认每个分组的第一个元素为已经有序的部分,A分组有序部分为 [1]，无序部分为[10,-4]；B分组有序部分为[9],无序部分为[8]。

• A分组的第一次比较：1和10比较，10大于1，交换10和1的位置。有序部分变为[10,1],无序部分为[-4].

• A分组的第二次比较：1和-4比较，1大于-4，不交换位置。A分组完全有序变为[10,9,1]。
  

• B分组的第一次比较：9和8比较，9大于8，不交换位置。B分组完全有序变为[9,8]。
  

• 对增量做处理，增量为1。第二次分组（得到C分组[10,9,1,8,-4]）,默认分组的第一个元素为已经有序的部分，C分组有序部分为[10]，无序部分为[9,1,8,-4]。

• C分组的第一次比较：10和9比较，10大于9，不交换位置。有序部分变为[10,9]。

• C分组的第二次比较：9和1比较，9大于1，不交换位置。有序部分变为[10,9,1]。

• C分组的第三次比较：1和8比较，1小于8，交换位置；

• C分组的第四次比较：8继续与9比较，9大于8，不交换位置。有序部分变为[10,9,8,1]。

• C分组的第五次比较：1和-4比较，1大于-4，不交换位置，有序部分变为[10,9,8,1,-4]。

• 对增量做处理，增量变为0，不满于大于1，结束分组(即结束排序操作)。
  

4.算法分析

    从上面排序流程，可以看到，对于一个包含n个元素的无序数组，我们使用n / 2设置初始的增量，根据增量将数组分成多个小组，分别对这些小组进行插入排序操作，每轮对所有小组排序完成后，对增量执行 (增量 / 2)操作,继续对分组后的数据进行插入排序操作，直到增量<1之后，结束排序流程。所以我们可以使用增量>=1，控制是否需要进行分组操作，在对每个分组中的数据执行插入排序操作。

5.算法实现

<?php$arr = [9, 1, 2, 5, 7, 4, 8, 6, 3, 5];$length = count($arr);
//获取增列序列$h = 1;while ($h < intval($length / 2)) { $h = 2 * $h + 1;}//希尔排序while ($h >= 1) { for ($i = $h; $i < $length; $i++) { for ($j = $i; $j >= $h; $j = $j - $h) { if ($arr[$j] > $arr[$j - $h]) { $temp = $arr[$j]; $arr[$j] = $arr[$j - $h]; $arr[$j - $h] = $temp; } else { break; } } } $h = intval($h / 2);}print_r($arr);

6.希尔排序的优点

    希尔排序其实就是变异的插入排序，只是相比插入排序每次比较只能移动一个位置的情况做出了改变，通过增量对数据进行分组的方式，使每次比较可以跨越多个数据位置，通过这种分组排序的方式，使无序数据变得部分有序起来，最后再对这个部分有序的数据实现基本的插入排序操作，这样就可以提高整个排序算法的执行效率。

希尔排序是基于插入排序的下面两个特质而进行改进的：

• 插入排序对基本有序的数据排序时，算法效率最高，可以达到O(n)。

• 插入排序同时也是低效的，因为每次只能移动一个位置。

7.时间复杂度

    希尔排序的时间复杂度依赖增量的选择会带来不同的时间复杂度，常见的增量有下面几种：

• 希尔增量： {n / 2, (n / 2) / 2, ..., 1 }

• Knuth增量：h(1) = 1, .., h(i) = 3 * h(i - 1) + 1

• Hibbard增量：h(1) = 1, h(i) = 2 * h(i - 1) + 1

当增量为1时，希尔排序退化为插入排序，再根据数据的有序情况，最好情况下时间复杂度为O(n),最坏时间复杂度为O(n²)。当增量不为1时，时间复杂度根据增量不同，会产生不同的结果，总结：希尔排序的时间复杂度在O(nlogn)和O(n²)之间，主要取决于增量的选择。

参考：

https://www.zhihu.com/question/24637339（一定要看这个问题下的冒泡的回答，简单易懂，太牛了。）