「排序算法」专题 11:希尔排序(不建议多花时间了解)
希尔排序的参考资料是《算法 4》。
- 思想来源:插入排序的优化。在插入排序里,如果靠后的数字较小,它来到前面就得交换多次。「希尔排序」改进了这种做法。带间隔地使用插入排序,直到最后「间隔」为 $1$ 的时候,就是标准的「插入排序」,此时数组里的元素已经「几乎有序」了;
- 希尔排序的「间隔序列」其实是一个超参数,这方面有一些研究成果,有兴趣的朋友可以了解一下,但是如果这是面向笔试面试,就不用了解了。
参考代码 6:
public class Solution {
// 希尔排序
public int[] sortArray(int[] nums) {
int len = nums.length;
int h = 1;
// 使用 Knuth 增量序列
// 找增量的最大值
while (3 * h + 1 < len) {
h = 3 * h + 1;
}
while (h >= 1) {
// insertion sort
for (int i = h; i < len; i++) {
insertionForDelta(nums, h, i);
}
h = h / 3;
}
return nums;
}
/**
* 将 nums[i] 插入到对应分组的正确位置上,其实就是将原来 1 的部分改成 gap
*
* @param nums
* @param gap
* @param i
*/
private void insertionForDelta(int[] nums, int gap, int i) {
int temp = nums[i];
int j = i;
// 注意:这里 j >= deta 的原因
while (j >= gap && nums[j - gap] > temp) {
nums[j] = nums[j - gap];
j -= gap;
}
nums[j] = temp;
}
}
希尔排序的时间复杂度至今还没有明确的结论,只有一个范围,已经不在我能介绍的范围了。
(本节完)