姬長信(Redy)

十大排序算法之希尔排序

本文首发于[个人博客](https://ityongzhen.github.io/十大排序算法之希尔排序.html) ## 前言 本系列排序包括十大经典排序算法。 ![](https://cocoachina.oss-cn-beijing.aliyuncs.com/article/59484315733870216070.png) - 使用的语言为/uff1aJava - 结构为/uff1a 定义抽象类`Sort`里面实现了/uff0c交换/uff0c大小比较等方法。例如交换两个值/uff0c直接传入下标就可以了。其他的具体排序的类都继承抽象类`Sort`。这样我们就能专注于算法本身。 ~~~~ /* * 返回值等于0/uff0c代表 array[i1] == array[i2] * 返回值小于0/uff0c代表 array[i1] < array[i2] * 返回值大于0/uff0c代表 array[i1] > array[i2] */ protected int cmp(int i1, int i2) { return array[i1].compareTo(array[i2]); } protected int cmp(T v1, T v2) { return v1.compareTo(v2); } protected void swap(int i1, int i2) { T tmp = array[i1]; array[i1] = array[i2]; array[i2] = tmp; } ~~~~ ## 什么是希尔排序 - [希尔排序](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F)/uff08Shellsort/uff09也称递减增量排序算法/uff0c是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 ## 改进 希尔排序是基于插入排序的以下两点性质而提出改进方法的/uff1a - 插入排序在对几乎已经排好序的数据操作时/uff0c效率高/uff0c即可以达到线性排序的效率 - 但插入排序一般来说是低效的/uff0c因为插入排序每次只能将数据移动一位 ## 希尔排序的历史 希尔排序按其设计者希尔/uff08Donald Shell/uff09的名字命名/uff0c该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner/uff0c即包含Marlene Metzner Norton的名字/uff0c但是根据Metzner本人的说法/uff0c/u201c我没有为这种算法做任何事/uff0c我的名字不应该出现在算法的名字中。/u201d ## 算法实现 - 原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。 V. Pratt的书对算法进行了少量修改/uff0c可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。 - 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序/uff0c算法的最后一步就是普通的插入排序/uff0c但是到了这步/uff0c需排序的数据几乎是已排好的了/uff08此时插入排序较快/uff09。 - 假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序/uff08冒泡排序或插入排序/uff09/uff0c可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据/uff0c所以小数据只需进行少数比较和交换即可到正确位置。 - 一个更好理解的希尔排序实现/uff1a将数组列在一个表中并对列排序/uff08用插入排序/uff09。重复这过程/uff0c不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法/uff0c算法本身仅仅对原数组进行排序/uff08通过增加索引的步长/uff0c例如是用`i += step_size`而不是`i++ `/uff09。 - 例如/uff0c假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]/uff0c如果我们以步长为5开始进行排序/uff0c我们可以通过将这列表放在有5列的表中来更好地描述算法/uff0c这样他们就应该看起来是这样/uff1a ~~~~ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ~~~~ 然后我们对每列进行排序/uff1a ~~~~ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ~~~~ 将上述四行数字/uff0c依序接在一起时我们得到/uff1a[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了/uff0c然后再以3为步长进行排序/uff1a ~~~~ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ~~~~ 排序之后变为/uff1a ~~~~ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 ~~~~ 最后以1步长进行排序/uff08此时就是简单的插入排序了/uff09。 ### 算法稳定性 - 希尔排序不是一种稳定排序算法。 ### 是否是原地算法 - 何为原地算法/uff1f - 不依赖额外的资源或者依赖少数的额外资源/uff0c仅依靠输出来覆盖输入 - 空间复杂度为 /ud835/udc42(1) 的都可以认为是原地算法 - 非原地算法/uff0c称为 Not-in-place 或者 Out-of-place - 希尔排序属于 In-place ### 时空复杂度 - 最好时间复杂度/uff1aO(n) - 最坏时间复杂度/uff1aO(n4/3)~O(n2) - 平均时间复杂度/uff1a取决于步长 - 空间复杂度/uff1aO(1) ## 步长序列 - 希尔本人给出的步长序列/uff0c最坏情况时间复杂度是O(n2) - 希尔给出的步长序列为1,2,4,8,16,32,64... - 目前已知的最好步长序列/uff0c最快情况时间复杂度为O(n4/3)/uff0c是在1986年由Robert Sedgewick提出的。 - 1/uff0c5/uff0c19/uff0c41/uff0c109... - Robert Sedgewick给出的步长序列实现如下 ~~~~ /* 获取最优步长 */ private List sedgewickStepSequence() { List stepSequence = new LinkedList<>(); int k = 0, step = 0; while (true) { if (k % 2 == 0) { int pow = (int) Math.pow(2, k >> 1); step = 1 + 9 * (pow * pow - pow); } else { int pow1 = (int) Math.pow(2, (k - 1) >> 1); int pow2 = (int) Math.pow(2, (k + 1) >> 1); step = 1 + 8 * pow1 * pow2 - 6 * pow2; } if (step >= array.length) break; stepSequence.add(0, step); k++; } return stepSequence; } ~~~~ ## 代码 ### 最简单的插入排序为基础/uff0c步长为1/uff0c2/uff0c4/uff0c8/uff0c16/uff0c32... ~~~~ public class ShellSort > extends Sort { @Override protected void sort() { // TODO Auto-generated method stub List stepSequence = sedgewickStepSequence(); for (Integer step : stepSequence) { sort(step); } } /** * 分成step列进行排序 */ private void sort(int step) { // col : 第几列/uff0ccolumn的简称 for (int col = 0; col < step; col++) { // 对第col列进行排序 // col、col+step、col+2*step、col+3*step for (int begin = col + step; begin < array.length; begin += step) { int cur = begin; while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur - step); cur -= step; } } } } /* 获取步长序列 */ private List shellStepSequence() { List stepSequence = new ArrayList<>(); int step = array.length; while ((step >>= 1) > 0) { stepSequence.add(step); } return stepSequence; } } ~~~~ ### 优化 思路/uff1a - 按照安卓[十大排序算法之插入排序](https://ityongzhen.github.io/十大排序算法之插入排序.html)中的/uff0c对插入排序算法进行优化 - 对步长进行优化 ~~~~ private void sort2(int step) { // col : 第几列/uff0ccolumn的简称 for (int col = 0; col < step; col++) { // 对第col列进行排序 for (int begin = step+col; begin < array.length; begin+=step) { int cur = begin; T res =array[cur]; while (cur>col && cmp(res,array[cur-step])<0) { array[cur] = array[cur-step]; cur-=step; } array[cur] = res; } } } ~~~~ ~~~~ /* 获取最优步长 */ private List sedgewickStepSequence() { List stepSequence = new LinkedList<>(); int k = 0, step = 0; while (true) { if (k % 2 == 0) { int pow = (int) Math.pow(2, k >> 1); step = 1 + 9 * (pow * pow - pow); } else { int pow1 = (int) Math.pow(2, (k - 1) >> 1); int pow2 = (int) Math.pow(2, (k + 1) >> 1); step = 1 + 8 * pow1 * pow2 - 6 * pow2; } if (step >= array.length) break; stepSequence.add(0, step); k++; } return stepSequence; } ~~~~ ### 优化过的代码为 ~~~~ package YZ.Sort; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ShellSort > extends Sort { @Override protected void sort() { // TODO Auto-generated method stub List stepSequence = sedgewickStepSequence(); for (Integer step : stepSequence) { sort2(step); } } /** * 分成step列进行排序 */ private void sort(int step) { // col : 第几列/uff0ccolumn的简称 for (int col = 0; col < step; col++) { // 对第col列进行排序 // col、col+step、col+2*step、col+3*step for (int begin = col + step; begin < array.length; begin += step) { int cur = begin; while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur - step); cur -= step; } } } } private void sort2(int step) { // col : 第几列/uff0ccolumn的简称 for (int col = 0; col < step; col++) { // 对第col列进行排序 for (int begin = step+col; begin < array.length; begin+=step) { int cur = begin; T res =array[cur]; while (cur>col && cmp(res,array[cur-step])<0) { array[cur] = array[cur-step]; cur-=step; } array[cur] = res; } } } /* 获取步长序列 */ private List shellStepSequence() { List stepSequence = new ArrayList<>(); int step = array.length; while ((step >>= 1) > 0) { stepSequence.add(step); } return stepSequence; } /* 获取最优步长 */ private List sedgewickStepSequence() { List stepSequence = new LinkedList<>(); int k = 0, step = 0; while (true) { if (k % 2 == 0) { int pow = (int) Math.pow(2, k >> 1); step = 1 + 9 * (pow * pow - pow); } else { int pow1 = (int) Math.pow(2, (k - 1) >> 1); int pow2 = (int) Math.pow(2, (k + 1) >> 1); step = 1 + 8 * pow1 * pow2 - 6 * pow2; } if (step >= array.length) break; stepSequence.add(0, step); k++; } return stepSequence; } } ~~~~ ## 结果 ### 数据源/uff1a 从1到20000之间随机生成10000个数据来测试 >Integer[] array = Integers.random(20000, 1, 80000); > ### 结果如下 【MergeSort】 稳定性/uff1atrue 耗时/uff1a0.011s(11ms) 比较次数/uff1a26.10万 交换次数/uff1a0 【QuickSort】 稳定性/uff1afalse 耗时/uff1a0.012s(12ms) 比较次数/uff1a34.55万 交换次数/uff1a1.32万 【HeapSort】 稳定性/uff1afalse 耗时/uff1a0.018s(18ms) 比较次数/uff1a51.10万 交换次数/uff1a2.00万 【ShellSort】 稳定性/uff1afalse 耗时/uff1a0.02s(20ms) 比较次数/uff1a43.04万 交换次数/uff1a0 【SelectionSort】 稳定性/uff1atrue 耗时/uff1a0.485s(485ms) 比较次数/uff1a2.00亿 交换次数/uff1a2.00万 【InsertionSort3】 稳定性/uff1atrue 耗时/uff1a0.526s(526ms) 比较次数/uff1a25.80万 交换次数/uff1a0 【InsertionSort2】 稳定性/uff1atrue 耗时/uff1a0.801s(801ms) 比较次数/uff1a9963.29万 交换次数/uff1a0 【InsertionSort1】 稳定性/uff1atrue 耗时/uff1a1.281s(1281ms) 比较次数/uff1a9963.29万 交换次数/uff1a9961.29万 【BubbleSort2】 稳定性/uff1atrue 耗时/uff1a2.271s(2271ms) 比较次数/uff1a2.00亿 交换次数/uff1a9961.29万 【BubbleSort】 稳定性/uff1atrue 耗时/uff1a2.339s(2339ms) 比较次数/uff1a2.00亿 交换次数/uff1a9961.29万 【BubbleSort1】 稳定性/uff1atrue 耗时/uff1a2.403s(2403ms) 比较次数/uff1a2.00亿 交换次数/uff1a9961.29万 可以看到希尔排序的性能还是很不错的/uff0c对比插入排序/uff0c优化的还是挺多的。 ## 逆序对 ### 什么是逆序对/uff1f 数组[2,4,1]中的逆序对为<2,1> 和 <4,1> ### 插入排序的时间复杂度和逆序对的数量成正比关系 逆序对越多/uff0c插入排序的时间复杂度越高 ### 当逆序对的数量极少时候/uff0c插入排序的效率特别高 甚至有时候可以比O(nlogn)级别的快速排序还要快 ## 代码地址/uff1a - 文中的代码在git上/uff1a[github地址](https://github.com/ITyongzhen/DataStructureAndAlgorithm)

退出移动版