排序算法之希尔排序
希尔排序
希尔排序是优化后的插入排序，又名玄学排序，因为希尔排序是不稳定的。希尔排序就是将一个数组分成间隔为h的子数组，并对这些子数组进行插入排序，通过不断地缩小h的值，从而满足插入排序适合的情形：数组基本有序，从而达到良好的性能。
难点
希尔排序的难点在于递增序列的选择，我使用的是《算法(第四版)》中推荐的递增序列，即1/2(3k-1)，从N/3开始递减至1。
演示
动图演示
代码实现
希尔排序的代码与插入排序相似，只是增加了一个增量h
int N = t.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >=1) {
for (int i = h; i < t.length; i++) {
int key = t[i];
int j = i - h;
while (j >= 0 && t[j] > key) {
t[j + h] = t[j];
j -= h;
}
t[j + h] = key;
}
h /= 3;
}总结
通过对希尔排序运行时间的测试，发现希尔排序比插入排序和选择排序要快很多，尤其是数组越大的时候。希尔排序最坏运行时间为O（n2），最好运行时间为O(n)，平均运行时间为O(n1.3)。有经验的程序员有时会用到希尔排序，因为对于中等大小的数组，它的运行时间是可以被接受的，并且不占用额外的空间。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/12/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
