希爾排序就這么簡單

paulli3 發布于2019-08-19 10:43 / 424人閱讀

摘要：這時就用簡單插入排序將數列直至已序從直觀上看希爾排序就是把數列進行分組不停使用插入排序，直至從宏觀上看起來有序，最后插入排序起來就容易了無須多次移位或交換。

一、希爾排序介紹

來源百度百科：

希爾排序(Shell"s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因D.L.Shell于1959年提出而得名。

從上面我們很容易看出來，它是插入排序的高級版

回顧一下插入排序：

將數據插入到已有序的數列中

排序前：將每個元素看成有序的數列

第一趟排序后：得到一個有序數列，其大小為2

第二趟排序后：得到一個有序數列，其大小為3

第三趟排序后：得到一個有序數列，其大小為4

........每一趟插入排序，都可以將一個無序值插入一個有序數列，直至全部值有序

如果給出的數組足夠亂的話，那么插入排序所耗費的時間是O(n^2)

既然希爾排序是插入排序的高級版，那它做了哪些優化呢？？讓我們來看看：

希爾排序在排序前：將一個序列分成了好幾個序列

在第一趟排序時：將這幾個序列做插入排序。排序后，部分較大的數字往后靠，部分較小的數字往前靠

在第二趟排序時：將這個序列又分了好幾個序列做插入排序(但比第一次分的數要少,ps:如果第一次分5個，第二次可能就2個了)。排序后，部分較大的數字往后靠，部分較小的數字往前靠

................

在第n趟排序時：將這個序列又分了好幾個序列(直到剩下一個序列)，從宏觀上看，此序列就基本是有序的了。這時就用簡單插入排序將數列直至已序

從直觀上看希爾排序：

就是把數列進行分組(不停使用插入排序)，直至從宏觀上看起來有序，最后插入排序起來就容易了(無須多次移位或交換)。

那么，上面那里說了將一個序列分成好幾個序列，那么到底怎么分呢？比如有10個元素的序列，分成幾個才合適？每次縮減又是多少呢？

從專業的角度上講，將一個序列分成好幾個序列，用一個數來表示：那個數稱為增量。顯然的是，增量是不斷遞減的(直到增量為1)

往往的：如果一個數列有10個元素，我們第一趟的增量是5，第二趟的增量是2，第三趟的增量是1。如果一個數列有18個嚴肅，我們第一趟的增量是9，第二趟的增量是4，第三趟的增量是2，第四趟的增量是1

很明顯我們可以用一個序列來表示增量：{n/2,(n/2)/2...1}，每次增量都/2

二、希爾排序體驗

現在我們有一個數組，該數組有6個元素

      int[] arrays = {2, 5, 1, 3, 4, 6};

排序前：

將該數組看成三個（arrays.length/2)數組，分別是:{2,3},{5,4},{1,6}

第一趟排序：

對三個數組分別進行插入排序，因此我們三個數組得到的結果為{2,3},{4,5},{1,6}

此時數組是這樣子的：{2, 4, 1, 3, 5, 6}

第二趟排序：

增量減少了，上面增量是3，此時增量應該為1了，因此把{2, 4, 1, 3, 5, 6}看成一個數組(從宏觀上是有序的了)，對其進行插入排序，直至有序

可能我舉的例子不夠好(沒看到很好的效果)，我們來看看網上的圖片，加深一下希爾排序的過程：

PS:圖片來源網上(侵刪)

三、希爾排序代碼實現


    public static void shellSort(int[] arrays) {


        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {

            //從增量那組開始進行插入排序，直至完畢
            for (int i = step; i < arrays.length; i++) {

                int j = i;
                int temp = arrays[j];

                // j - step 就是代表與它同組隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
        }


    }

我們發現希爾排序代碼其實非常簡單(相比對堆排序)，理解起來也不難，就用增量來將數組進行分隔，直到增量為1。底層干的還是插入排序干的活～

四、最后

參考資料：

http://blog.csdn.net/jianfpeng241241/article/details/51707618

http://blog.csdn.net/robomaster/article/details/50953265

https://www.cnblogs.com/chengxiao/p/6104371.html

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y

云服務器 GPU云服務器希爾排序最簡單的排序算法簡單的c語言排序希爾

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76359.html

八大基礎排序總結

摘要：不斷執行這個操作代碼實現快速排序用遞歸比較好寫如果不太熟悉遞歸的同學可到遞歸就這么簡單。前言大概花了一周的時間把八大基礎排序過了一遍，這篇博文主要是用來回顧一下八大基礎排序的要點和一些總結～回顧：冒泡排序就這么簡單選擇排序就這么簡單插入排序就這么簡單快速排序就這么簡單歸并排序就這么簡單堆排序就這么簡單希爾排序就這么簡單基數排序就這么簡單總的來說：快速排序是用...

maochunguang 2019-08-16 11:07 評論0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...

verano 2019-08-20 15:08 評論0 收藏0
基本算法學習(一)之希爾排序(JS)

摘要：動態定義間隔序列參考來源詳細介紹了十種算法大家可以去學習下以后大概會盡量每天更新一個算法學習吧溫故而知新參考書:嚴蔚敏-數據結構希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點: 內排序(內存排序就夠了) 不穩定(排序后原始順序無法保證) 希爾排序重點在于分割. 基本思想: 將整個待排序記錄序...

cooxer 2019-08-20 11:09 評論0 收藏0
數據結構與算法——希爾、歸并、快速排序

摘要：今天再來看看另外三種時間復雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數取中法求將放到數組的末尾總結這三種排序算法的平均時間復雜度都是，歸并排序和快速排序的應用更廣泛。 1. 回顧前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時間復雜度都是 O(n2)，比較的高，適合小規模的數據排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...

hersion 2019-08-16 15:58 評論0 收藏0