排序算法-希尔排序(Shell Sort)
文章目录
- 希尔排序法介绍
- 希尔排序法算法
- 时间复杂度
- 稳定性
- 其他排序法的比较
希尔排序法介绍
希尔排序法(Shell Sort)是D.L.Shell于1959年提出的一种排序算法，是直接插入排序法的更高效的改进版。在这之前的排序算法如冒泡排序、简单选择排序、直接插入排序等算法的的时间复杂度都为 O ( n 2 ) O(n^{2}) O(n2)，而希尔排序突破了这一时间复杂度。
【原理】
直接插入排序算法比冒泡排序和简单选择排序性能都要高，尤其在序列基本有序并且记录数相对较少的情况，只需要简单的几个插入动作就能完成排序。
希尔排序的思路就是在插入排序算法的基础上，创造插入排序算法的有利条件，将序列按照某个增量分成多个子序列进行插入排序，使整个序列变为基本有序，并且由于按照增量分了子序列，所以每个子序列的记录数变少了，增量和子序列长度成反比，增量从小于n的某个值每次递减，子序列随增量变小而变长。直到增量变为1，使其所有记录为一个整体序列然后进行一次插入排序为止。
什么才叫基本有序呢？比如{2,1,4,3,5,6,8,7,9}可以说是基本有序，小的数字基本在序列的前部，不大不小的在中部，大的数字在后部。 {8,7,6,3,9,2,4,5,1}这样的序列就不是基本有序，因为1在序列的最后，9在中间，8在第一位，所以谈不上是基本有序的。
【例子】
下面看个对关键字序列{8,7,1,9,3,6,4,5,2}进行希尔排序的步骤。
希尔排序法算法
public static void shellSort(Integer[] arr) {int increment = arr.length;do {increment = increment / 3 + 1;for (int i = increment; i < arr.length; i++) {if (arr[i-increment] > arr[i]){int minIdx = i;int compIdx = minIdx-increment; //需往右边移动的关键字下标int minValue = arr[minIdx];while (compIdx >= 0 && arr[compIdx] > minValue) { //比较大小arr[minIdx] = arr[compIdx]; //关键字右移minIdx = compIdx;compIdx = compIdx - increment;}arr[minIdx] = minValue; //插入关键字}}} while (increment > 1);}
时间复杂度
希尔排序的时间复杂度依赖增量序列，增量的取值至今还是个难题，大量研究表明，当增量序列为delta[k]= 2 t − k + 1 2^{t-k+1} 2t−k+1-1(0 ⩽ \leqslant ⩽k ⩽ \leqslant ⩽t ⩽ ⌊ l o g 2 ( n + 1 ) ⌋ \leqslant \left \lfloor log2(n+1) \right \rfloor ⩽⌊log2(n+1)⌋) 时，可以获得不错的效率，其时间复杂度为 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2)，要好于直接插入排序的 O ( n 2 ) O(n^{2}) O(n2)。
稳定性
由于按照增量跳跃式分成了子序列插入排序，所以相同值位置可能会被替换，所以希尔排序是不稳定的。
其他排序法的比较
以下分别使用简单选择排序法、直接插入排序法和希尔排序法对10万随机关键字的排序耗时，从结果可以看出直接插入排序的执行时间比简单选择排序法快，而希尔排序法比直接插入排序法快了非常多只用了38ms。
简单选择排序执行时间:8077ms直接插入排序执行时间:4408ms希尔排序执行时间:38ms
逃离我推掉我的手
灰太狼
ゞ 浴缸里的玫瑰
╰+攻爆jí腚メ
红太狼
你的名字
还没有评论，来说两句吧...