希尔排序是非稳定排序算法。
平均时间复杂度O(nlogn),空间复杂度O(1)
最坏时间复杂度跟选取的增量序列有关,最佳为O(n3/2)
适用于直接插入排序问题,数据量巨大时。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。
步骤如下:
重复第二步,直到k=1执行简单插入排序。
希尔排序耗时的操作有:比较 + 后移赋值。
时间复杂度情况如下:(n指待排序序列长度)
最坏情况:O(n^2)。(当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(n²))
渐进时间复杂度(平均时间复杂度):O(nlog2n)
希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。上面选择的增量序列{n/2,(n/2)/2...1}(希尔增量),其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)
实现:
C++
void shellsort(int a[], int n) { int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) swap(a[j], a[j + gap]); }
上面希尔排序的步长选择都是从n/2开始,每次再减半,直到最后为1。其实也可以有另外的更高效的步长选择,请参阅维基百科上对希尔排序步长的说明。
原文:https://www.cnblogs.com/shona/p/12582908.html