阿里朋友的忠告：大厂里算法很重要，先来了解一下希尔排序
共 1495字，需浏览 3分钟
· 2022-07-12
一、希尔排序介绍
希尔排序这个名字，来源于它的发明者希尔，也称作“缩小增量排序”，是插入排序的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1、插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
二、对数组使用希尔排序
首先，选择增量 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式
初始增量为 gap = 10/2 = 5，整个数组分成了 5 组
按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0】
对这分开的 5 组分别使用插入排序
结果可以发现，这五组中的相对小元素都被调到前面了
缩小增量 gap = 5/2 = 2，整个数组分成了 2 组
【 3 , 1 , 0 , 9 , 7 】，【 5 , 6 , 8 , 4 , 2 】
对这分开的 2 组分别使用上节所讲的插入排序
此时整个数组的有序性是很明显的
再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组
【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0 】
此时，只需要对以上数列进行简单的微调，不需要大量的移动操作即可完成整个数组的排序
public static void shellSort(Comparable[] arr) {int j;for (int gap = arr.length / 2; gap > 0; gap /= 2) {for (int i = gap; i < arr.length; i++) {Comparable tmp = arr[i];for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {arr[j] = arr[j - gap];}arr[j] = tmp;}}}
复习插入排序
private static void sort(Comparable[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {for (int j = i; j > 0; j--) {if (arr[j].compareTo(arr[j - 1]) < 0) {swap(arr, j, j - 1);} else {break;}}}}private static void swap(Object[] arr, int i, int j) {Object t = arr[i];arr[i] = arr[j];arr[j] = t;}
三、时间复杂度
性能比较
随机生成长度为100的数组，对比插入排序和希尔排序的性能：
四、适用场景
希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。