希尔排序
前面我们说过了插入排序，它是三种基本排序中最常用的一种排序，具有排序稳定，空间复杂度低，而且在样本小且基本有序时效率比较高，该篇讲述的希尔排序是对插入排序的一种优化排序，在希尔排序开始阶段，通过增量的方式使排序的样本小化，在希尔排序的最后阶段蜕变成插入排序，但可以完美实现样本基本有序，从而使得对样本的排序相比于直接使用插入排序，在很大程度上得到优化。
希尔排序中存在一个关键因素——增量，通过增量的存在将原数组分解成多个子数组，然后在每个子数组中使用插入排序来使元素有序化，一轮排序过后，缩小增量值，按上述方式继续对重新得到的子数组进行排序，最后增量会变为1，此时就是对整个数组进行最后的一轮排序，最后得到的就是经过希尔排序之后的有序数组。
假定初始数组为：{2,5,7,1,3,4,6}
人为设置初始增量为4，那么得到的四个子数组为：{2,3}、{5,4}、{7,6}、{1}
每个子数组经过插入排序之后得到的数组为：{2,4,6,1,3,5,7}
将增量变为2，那么得到的两个子数组为：{2,6,3,7}、{4,1,5}
每个子数组经过插入排序之后得到的数组为：{2,1,3,4,6,5,7}
将增量变为1，进行最后一轮的插入排序得到的结果为：{1,2,3,4,5,6,7}
对应的算法代码为：
private static void shell(int[] arr) {
int gap = 4;
for (; gap >= 1; gap >>= 1) {
for (int i = gap; i < arr.length; i++) { //从gap处开始遍历，gap之前的值都是各数组第一个值，单值数组直接就是有序的
for (int j = i; j > gap - 1; j -= gap) { //每次都跳过gap长度与前一个值进行比较
if (arr[j - gap] > arr[j]) { //跳过gap长度的前一个值小于待插入值
Utils.swap(arr, j - gap, j); //交换
}
}
}
}
}
希尔排序关键的一点就在于增量的选择，直接使用1,2,4,8,16...的方式并不能最大限度的提高希尔排序的效率，网上也有很多其他的增量序列可以选择，这里提供一种Knuth序列的实现方式
//Knuth序列
n=1
n=3*n+1
序列：1,4,13,40,121...
使用Knuth序列对应的希尔排序代码为：
private static void shell(int[] arr) {
int gap = 1;
while (gap < arr.length / 3) {
gap = gap * 3 + 1; //按照Knuth序列增大增量值
}
for (; gap >= 1; gap = (gap - 1) / 3) { //按照Knuth序列减小增量值
for (int i = gap; i < arr.length; i++) {
for (int j = i; j > gap - 1; j -= gap) {
if (arr[j - gap] > arr[j]) {
Utils.swap(arr, j - gap, j);
}
}
}
}
}
测试排序结果
通过对数器的方式进行排序结果的验证
//测试代码
public static void main(String[] args) {
int size = 15;
int[] arr1 = Utils.generateRandomArray(size, 100);
int[] arr2 = new int[size];
System.arraycopy(arr1, 0, arr2, 0, size);
System.out.println("原数组： " + Arrays.toString(arr1));
Arrays.sort(arr1);
System.out.println("系统方法排序后： " + Arrays.toString(arr1));
shell(arr2);
System.out.println("希尔方法排序后： " + Arrays.toString(arr2));
}
原数组： [70, 49, 88, 24, 51, 36, 33, 17, 55, 16, 13, 79, 96, 75, 0]
系统方法排序后： [0, 13, 16, 17, 24, 33, 36, 49, 51, 55, 70, 75, 79, 88, 96]
希尔方法排序后： [0, 13, 16, 17, 24, 33, 36, 49, 51, 55, 70, 75, 79, 88, 96]
如果对你有帮助，点个赞，或者打个赏吧，嘿嘿
整理不易，请尊重博主的劳动成果