Java排序算法之——希爾排序

Enlightenment 發布于2019-08-14 12:21 / 1502人閱讀

摘要：算法簡述希爾排序也叫作排序或縮小增量排序，據說是一個叫的人發明出來的，顧取名排序。這種排序是基于插入排序思想的，也比較適用于數據量大時。

算法簡述

希爾排序也叫作shell排序或縮小增量排序，據說是一個叫D.L.Shell的人發明出來的，顧取名shell排序。這種排序是基于插入排序思想的，也比較適用于數據量大時。

我剛開始看到時候對于插入排序也是半瓶子醋，直接導致我看不懂了，抓狂，so...我就去默默的補習一下插入排序嘍。

插入排序簡介

插入排序的核心思想是比較和插入，就是從第二個數開始，依次插入到前面合適的位置。排序步驟如下：

1. 首先對數組的前兩個數據進行從小到大的排序
2. 接著將第3個數據與排序好的兩個數據進行比較，插入合適的位置
3. 然后，將第4個數據插入已經排好的前3個數據中
4. 不斷重復上述的過程，完成排序

代碼實現

private void insertSort(int[] a)
    {
        int i,j,t,h;
        for(i =1;i=0&&t
簡單的介紹了一下插入排序，下面就講一下這個希爾排序。
排序步驟
1.將有n個元素的數組分為n/2個數字序列，第1個數據和第n/2+1個數據為一對。。。
2.一次循環使每一個序列對排好順序（對每個序列使用插入排序算法，實質是一種分組插入）
3.然后，再變為n/4個序列，再次排序
4.不斷重復上述過程，隨著序列減少最后變為一個，也就完成了整個排序。

實例講解
比如對{12,31,11,20,17，30}進行希爾排序：
1. 第一次排序，首先將數組分為6/2=3個數字序列，第一個數據12和第四個數據20為一對，第二個數據和第五個數據為一對，第三個數據和第六個數據為一對，每一對進行排序后數據為：12,17,11,20,31,30
2. 第二次排序，將數組劃分為6/4=1（這里取整），此時逐個對數據比較，按照插入排序算法進行排序，排序后的數據為：11,12,17,20,30,31

代碼片段
private void shellSort(int[] a)
    {
        int i,j,h;
        int r,temp;
        int x = 0;
        for(r = a.length/2;r>=1;r/=2)
        {
            for(i = r;i=0&&temp
至此希爾排序就完成了，時間復雜度為O(nlog2n).

云服務器 GPU云服務器希爾排序 java插入排序算法 java實驗排序算法 java自然排序算法

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

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

糊涂算法之「八大排序」總結——用兩萬字，8張動圖，450行代碼跨過排序這道坎（建議收藏）

摘要：今天，一條就帶大家徹底跨過排序算法這道坎，保姆級教程建議收藏。利用遞歸算法，對分治后的子數組進行排序。基本思想堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為，它也是不穩定排序。 ...

greatwhole 2021-09-28 09:36 評論0 收藏0
基本算法學習(一)之希爾排序(JS)

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

cooxer 2019-08-20 11:09 評論0 收藏0
排序算法（Java）——那些年面試常見的排序算法

摘要：下面會介紹的一種排序算法快速排序甚至被譽為世紀科學和工程領域的十大算法之一。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。為了展示初級排序算法性質的價值，我們來看一下基于插入排序的快速的排序算法希爾排序。前言　　排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 評論0 收藏0
七大排序算法總結(java)

摘要：前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。直到無序區中的數為零，結束排序。步驟以從小到大為例，排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的，其中每一個堆都是完全二叉樹。前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。排序方法平均復雜度最壞復雜度最好復雜度輔助空間穩定性直接選擇排序 O(n^2...

cartoon 2019-08-14 14:09 評論0 收藏0
希爾排序就這么簡單

摘要：這時就用簡單插入排序將數列直至已序從直觀上看希爾排序就是把數列進行分組不停使用插入排序，直至從宏觀上看起來有序，最后插入排序起來就容易了無須多次移位或交換。一、希爾排序介紹來源百度百科：希爾排序(Shells Sort)是插入排序的一種又稱縮小增量排序（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方...

paulli3 2019-08-19 10:43 評論0 收藏0