首页 java基础 数据结构与算法

# 排序 - Shell 排序 (Shell Sort)

希尔排序 (Shell Sort) 是插入排序的一种，它是针对直接插入排序算法的改进。

# 希尔排序介绍

希尔排序实质上是一种分组插入方法。它的基本思想是：对于 n 个待排序的数列，取一个小于 n 的整数 gap (gap 被称为步长) 将待排序元素分成若干个组子序列，所有距离为 gap 的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小 gap 的值，并重复执行上述的分组和排序。重复这样的操作，当 gap=1 时，整个数列就是有序的。

# 希尔排序实现

下面以数列 {80,30,60,40,20,10,50,70} 为例，演示它的希尔排序过程。

第 1 趟: (gap=4)

alg-sort-shell-1.jpg

当 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}。 对应数列:

第 2 趟: (gap=2)

alg-sort-shell-2.jpg

当 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}。 对应数列:

第 3 趟: (gap=1)

alg-sort-shell-3.jpg

当 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 个组分别进行排序，排序结果:

# 希尔排序的时间复杂度和稳定性

# 希尔排序时间复杂度

希尔排序的时间复杂度与增量 (即，步长 gap) 的选取有关。例如，当增量为 1 时，希尔排序退化成了直接插入排序，此时的时间复杂度为 O (N²)，而 Hibbard 增量的希尔排序的时间复杂度为 O (N3/2)。

# 希尔排序稳定性

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 O (n^2) 好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以 shell 排序是不稳定的。

算法稳定性 – 假设在数列中存在 a [i]=a [j]，若在排序之前，a [i] 在 a [j] 前面；并且排序之后，a [i] 仍然在 a [j] 前面。则这个排序算法是稳定的！

# 代码实现

package com.w.winterVacation.sort;
import java.util.Arrays;
/**
 * shell 排序
 * @author wspstart
 * @create 2023-01-25 17:23
 */
public class ShellSort {
    public static void sort(int[] arr){
        for (int gap = arr.length / 2; gap > 0 ; gap = gap / 2) {
            // 分组插入排序
            for (int i = gap; i < arr.length; i++) {
                // 记录当前正在插入的数据
                int temp = arr[i];
                int j;
                for ( j = i; j >=gap  && greater(arr[j - gap],temp); j= j-gap) {
                    arr[j] = arr[j-gap];
                }
                arr[j] = temp;
            }
            println(gap,arr);
        }
    }
    /**
     * 比较 v 元素是否大于 w 元素
     *
     * @param v
     * @param w
     * @return
     */
    private static boolean greater(int v, int w) {
        return v > w;
    }
    /**
     * 数组元素 i 和 j 交换
     *
     * @param a
     * @param i
     * @param j
     */
    private static void exch(int[] a, int i, int j) {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    private static void println(int num, int[] a) {
        System.out.println("第" + num + "次循环" + Arrays.toString(a));
    }
}