statement：本篇内容只是建立在我目前经验的基础之上，必然有不完善甚至是不正确的地方，请谨慎阅读，如果能指出错误与不足之处，更是不甚感激
PS1：代码部分将使用Java语言进行展示
PS2：本节排序算法基于顺序表排序
一、原理
- 希尔排序可以简单理解为进行多次的直接插入排序
- 直接插入排序在待排序序列元素数量较少，待排序序列基本有序的情况下，拥有极高的效率，接近O(n)
- 按照上述规则，如果将待排序序列先分成多个小块各自排序，然后在整个序列有序程度较高的情况下，在进行一次完整的直接插入排序，那么排序效率将会得到显著提高
- 将排序序列分段也需要一定的策略，单纯的按照普通分段方式（即前面几个分为一段，后面几个分为一段），无法做到能够使整个序列在一次排序过后整体有序，只能做到每个部分有序
- 故希尔排序使用的是增量分段的策略，即按照一定的增量分段，如按2分段，就是第1、3、5、7、9、...分为一段，使用增量分段策略分段冰排序后，整个待排序序列能够获得一个整体有序的状态
二、代码
- Java代码
/**
* 本函数原理是简单插入排序，但是只对其中增量为increment的部分序列进行排序，主要用于希尔排序
* @param sortArray 待排序序列
* @param increment 增量
*/
private static void simpleInsertSortASCByIncrement(int[] sortArray , int increment) {
for(int i = increment ; i < sortArray.length ; i++) {//前面increment个序列对于其各自的下一个序列来说都是有序的，所以不用管
int j = i;
int temp = sortArray[i];
for(;j >= increment && temp < sortArray[j-increment]; j-=increment) {
sortArray[j] = sortArray[j-increment];
}
sortArray[j] = temp;
}
}
/**
* 希尔排序，增量序列算法为dlta[k] = 2^(t-k) + 1
* @param sortArray
*/
public static void shellInsertASC(int[] sortArray) {
//求得最大排序次数
int t= (int)(Math.log10(sortArray.length - 1)/Math.log10(2)) ;
//计算增量序列
List<Integer> incrementList = new ArrayList<Integer>();
int increment = 0;
for(int i = 0 ; increment != 1 ; i++) {
increment = (int) (Math.pow(2, t - i)) + 1;
incrementList.add(increment);
}
//按增量序列进行按增量分段的直接插入排序
for(int i = 0 ; i < incrementList.size() ; i++) {
simpleInsertSortASCByIncrement(sortArray, incrementList.get(i));
System.out.println(Arrays.toString(sortArray));
}
}
三、时间复杂度
希尔排序的时间复杂度和增量序列有关，上述的代码中使用的增量序列算法是dlta[k] = 2(t-k) + 1，t为执行的趟数。
参考文档：
[1] [数据结构C语言版 -- 清华大学出版社]
网友评论