排序算法圖解之Java希爾排序

更新時間：2022年11月06日 09:41:32 作者：興趣使然黃小黃

希爾排序是希爾(Donald?Shell)于1959年提出的一種排序算法，其也是一種特殊的插入排序，即將簡單的插入排序進行改進后的一個更加高效的版本，也稱縮小增量排序。本文通過圖片和示例講解了希爾排序的實現(xiàn)，需要的可以了解一下

1.希爾排序簡介

希爾排序是希爾(Donald Shell)于1959年提出的一種排序算法，其也是一種特殊的插入排序，即將簡單的插入排序進行改進后的一個更加高效的版本，也稱縮小增量排序。

希爾排序是非穩(wěn)定排序算法。把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至 1 時，整個文件恰被分成一組，算法便終止。

2.希爾排序算法圖解

以序列: {8, 9, 1, 7, 2, 3, 5, 6, 4, 0} 為例！

1.初始步長gap = length/2 ＝ 5，意味著將整個數(shù)組分為了5組，即[8，3]，[9，5]，[1，6]，[7，4]，[2，0]，對每組進行插入排序，得到序列：{3，5，1，4，0，8，9，6，7，2}，可以看到：3，5，4，0這些小元素都被提到前面了。

2.縮小增量gap = 5/2 = 2，數(shù)組被分為兩組，即[3，1，0，9，7]，[5，4，8，6，2]，對這兩組分別進行直接插入排序，可以看到，整個數(shù)組的有序程度更進一步了。

3.再次縮小增量，gap = 2/2 = 1，此時整個數(shù)組為[0，2，1，4，3，5，7，6，9，8]，進行一次插入排序，即可實現(xiàn)數(shù)組的有序化（僅需要簡單微調(diào)，而無需大量移動操作）。

3.希爾排序代碼實現(xiàn)

import java.util.Arrays;

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 希爾排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 6, 4, 0};
        System.out.println("排序前: " + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    //希爾排序
    public static void shellSort(int[] arr){
        //設(shè)定步長
        for (int gap = arr.length / 2; gap > 0; gap /= 2){
            //將數(shù)據(jù)分為arr.length/gap組，逐個對其所在的組進行插入排序
            for (int i = gap; i < arr.length; i++) {
                //遍歷各組中的所有元素，步長為gap
                int j = i;
                int temp = arr[j]; //記錄待插入的值
                while (j - gap >= 0 && temp < arr[j-gap]){
                    //移動
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //找到位置，進行插入
                arr[j] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}