希尔排序（Shell Sort）
一、算法概述
1.1 算法分类
十种常见排序算法可以分为两大类：
-
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
-
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
1.2 算法复杂度
1.3 相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
二、希尔排序（Shell Sort）
1959年Shell发明，第一个突破O(n²)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
2.1 算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
2.2 动图演示
Shell Sort
2.3 排序过程
下面以数列{80,30,60,40,20,10,50,70}为例，演示它的希尔排序过程。
第1趟：(gap=4)
当gap=4时,意味着将数列分为4个组： {80,20},{30,10},{60,50},{40,70}。 对应数列： {80,30,60,40,20,10,50,70}
对这4个组分别进行排序，排序结果： {20,80},{10,30},{50,60},{40,70}。 对应数列： {20,10,50,40,80,30,60,70}
第2趟：(gap=2)
当gap=2时,意味着将数列分为2个组：{20,50,80,60}, {10,40,30,70}。 对应数列： {20,10,50,40,80,30,60,70}
注意：{20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。
{10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。
对这2个组分别进行排序，排序结果：{20,50,60,80}, {10,30,40,70}。 对应数列： {20,10,50,30,60,40,80,70}
第3趟：(gap=1)
当gap=1时,意味着将数列分为1个组：{20,10,50,30,60,40,80,70}
注意：{20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。
对这1个组分别进行排序，排序结果：{10,20,30,40,50,60,70,80}
2.4 代码实现
/**
* @author: huangyibo
* @Date: 2021/11/17 17:05
* @Description: 希尔排序
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = {5, 9, 7, 4, 1, 3, 2, 8};
//shellSortV1(arr);
shellSortV2(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序 针对有序序列在插入时采用交换法
* @param arr
*/
public static void shellSortV2(int[] arr){
//增量gap，并逐步缩小增量
for(int gap = arr.length / 2; gap > 0; gap /= 2){
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(int i = gap; i < arr.length; i++){
int j = i;
while(j - gap >= 0 && arr[j] < arr[j-gap]){
//插入排序采用交换法
swap(arr,j,j-gap);
j -= gap;
}
}
}
}
/**
* 希尔排序 针对有序序列在插入时采用移动法。
* @param arr
*/
public static void shellSortV1(int[] arr){
//增量gap，并逐步缩小增量
for(int gap = arr.length / 2; gap > 0; gap /= 2){
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(int i = gap; i < arr.length; i++){
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-gap]){
while(j - gap >= 0 && temp < arr[j-gap]){
//移动法
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a,int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
}
2.5 算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
参考：
https://www.cnblogs.com/onepixel/articles/7674659.html
