希尔排序相当于直接插入排序的升级(分组插入排序),又称缩小增量排序,同属于插入排序类,不是稳定的排序算法。
比直接插入排序快的原因:
刚开始的时候间隔较大, 每个组里面的数据较少,排序很快
;当分隔加大的时候, 每组的数据变多, 但是因为已经有了前面的工作,数据接近于有序, 所以也很快
基本思想:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
C++代码
/**********************************/ /***********希尔排序***************/ /**********************************/ void ShellSort(ElemType a[],int n) { int i,j; int increment = n; do { increment = increment/3+1;//增量序列 for(i = increment+1;i<=n;i++) { if(a[i] < a[i-increment]) { int tmp = a[i]; for(j = i-increment;j > 0 && tmp < a[j];j -= increment) a[j+increment] = a[j]; a[j+increment] = tmp; } } } while(increment > 1); }
Python代码
#--------------# #--Shell sort--# #--------------# def shell_sort(arr): increment = len(arr); while increment > 1: increment = increment/3+1 shell_pass(arr,increment) def shell_pass(arr,increment): arrlen = len(arr) #for every subsequence which interval is increment for i in range(increment,arrlen): #keep value of arr[i],later may be changed by arr[i-increment] tmp = arr[i] k = i while k >= increment and arr[k-increment] > tmp: arr[k] = arr[k - increment] k -= increment arr[k] = tmp
希尔排序复杂度分析:
增量大小对效率影响非常大,现选用increment=increment/3+1的增量,时间复杂度为O(n^3/2),增量序列的最后一个增量值必须等于1.