何為希爾排序

這篇文章主要講解了“何為希爾排序”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“何為希爾排序”吧！

概述

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

• 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；

這個結論很明顯，如果一個數組大部分元素都有序，那么數組中的元素自然不需要頻繁地進行比較和交換。

• 在元素數量較少的情況下，插入排序的工作量較小

這個結論更加顯而易見，插入排序的工作量和n的平方成正比，如果n比較小，那么排序的工作量自然要小得多

也就是說：如果我們對數據做一些 “預處理”，使得原始數組的大部分元素變得有序，那么我們再使用插入算法進行排序，那么排序的效率將會大大提高。希爾排序正事基于這種思路實現的。

舉個栗子

這是我們現在拿到的原始數組：

第一輪，我們取總長度的一半，也就是4，作為跨度，這樣兩兩一組，總共事4組：

接下來，我們讓每組元素進行獨立排序，排序方式用直接插入排序即可。由于每一組的元素數量很少，只有兩個，所以插入排序的工作量很少。每組排序完成后的數組如下：

這樣一來，僅僅經過幾次簡單的交換，數組整體的有序程度得到了顯著提高，使得后續再進行直接插入排序的工作量大大減少。這種做法，可以理解為對原始數組的“粗略調整”。 但是這樣還不算完，我們可以進一步縮小分組跨度，重復上述工作。把跨度縮小為原先的一半，也就是跨度為2，重新對元素進行分組，一共兩組：

接下來，我們繼續讓每組元素進行獨立排序，排序方式用直接插入排序即可。每組排序完成后的數組如下：

最后，我們把分組跨度進一步減小，讓跨度為1，也就等同于做直接插入排序。經過之前的一系列粗略調整，直接插入排序的工作量減少了很多，排序結果如下：

讓我們重新梳理一下分組排序的整個過程：

代碼實現：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int step = arr.length / 2;
        for (; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                int temp = arr[i];
                int j = i;
                for (; j >= step && temp < arr[j - step]; j -= step) {
                    //符合條件往后移
                    arr[j] = arr[j - step];
                }
                arr[j] = temp;
            }
        }
        return arr;
    }

感謝各位的閱讀，以上就是“何為希爾排序”的內容了，經過本文的學習后，相信大家對何為希爾排序這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！