最近2018中文字幕在日韩欧美国产成人片_国产日韩精品一区二区在线_在线观看成年美女黄网色视频_国产精品一区三区五区_国产精彩刺激乱对白_看黄色黄大色黄片免费_人人超碰自拍cao_国产高清av在线_亚洲精品电影av_日韩美女尤物视频网站

【排序算法】—— 希爾排序

為亞東等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及亞東網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為成都做網(wǎng)站、網(wǎng)站制作、亞東網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！目錄

• 一、希爾排序原理
• • 1. 插入排序的問題
  • 2. 希爾排序的思路
• 二、希爾排序的相關問題
• • 1. 為什么插入排序那么多但效率卻很高
  • 2. 如何選擇希爾增量
• 三、代碼實現(xiàn)
• • 1. 代碼實現(xiàn)思路
  • 2. 實現(xiàn)代碼

希爾排序是對直接插入排序的優(yōu)化，在學習之前，沒有學過插入排序的童鞋們建議先學習插入排序：點擊跳轉到插入排序😜

一、希爾排序原理 1. 插入排序的問題

? 逆序有序的數(shù)組排序時，時間復雜度為 O ( n 2 ) O(n^2) O(n2)，此時效率最低

? 順序有序的數(shù)組排序時，時間復雜度為 O ( n ) O(n) O(n)，此時效率最高

? 我們發(fā)現(xiàn)，當被排序的對象越接近有序時，插入排序的效率越高，那我們是否有辦法將數(shù)組變成接近有序后再用插入排序，此時希爾大佬就發(fā)現(xiàn)了這個排序算法，并命名為希爾排序

2. 希爾排序的思路

? 希爾排序是對插入排序的優(yōu)化，基本思路是先選定一個整數(shù)作為增量，把待排序文件中的所有數(shù)據(jù)分組，以每個距離的等差數(shù)列為一組，對每一組進行排序，然后將增量縮小，繼續(xù)分組排序，重復上述動作，直到增量縮小為1時，排序完正好有序。

? 希爾排序原理是每一對分組進行排序后，整個數(shù)據(jù)就會更接近有序，當增量縮小為1時，就是插入排序，但是現(xiàn)在的數(shù)組非常接近有序，移動的數(shù)據(jù)很少，所以效率非常高，所以希爾排序又叫縮小增量排序。

? 每次排序讓數(shù)組接近有序的過程叫做預排序，最后一次插入是直接插入排序

1. 以3作為增量對數(shù)組進行分組，以下數(shù)組被分成3組，每組之間都是以3的等差數(shù)列

2. 對每一組進行插入排序，得到如下數(shù)組

3. 此時增量縮小，以2為增量對數(shù)組進行分組，數(shù)組被分成2份，每組之間都是2的等差數(shù)列

4. 對每一組進行插入排序，得到如下數(shù)組

5. 最后增量為1，分為1組（其實就等于沒分），對其進行插入排序，數(shù)組變得有序

二、希爾排序的相關問題 1. 為什么插入排序那么多但效率卻很高

1. 希爾排序中待排數(shù)據(jù)每次是以增量的移動步數(shù)空出插入位置，所以效率比普通插入一次一步的移動方式要快

2. 每一次排序之后數(shù)組就會變得接近有序，插入排序的移動次數(shù)就會越來越少，效率也不是普通的插入排序能比的了

3. 希爾排序移動次數(shù)：共移動8步

2. 直接插入排序移動次數(shù)：共移動15步

綜上所述：希爾排序在越大的數(shù)組上更能發(fā)揮優(yōu)勢，因為步子邁的更大，減少插入排序的移動次數(shù)更多

2. 如何選擇希爾增量

? 希爾排序的分析是一個復雜的問題，它的時間是一個關于增量序列的函數(shù)，這涉及到一些數(shù)學上未能攻克的難題，所以目前為止對于希爾增量到底怎么取也沒有一個最優(yōu)的值，但是經(jīng)過大量研究已經(jīng)有一些局部的結論，在這里并不展開敘述。

? 最初希爾提出的增量是gap = n / 2，每一次排序完讓增量減少一半gap = gap / 2，直到gap = 1時排序變成了直接插入排序。直到后來Knuth提出的gap = [gap / 3] + 1，每次排序讓增量成為原來的三分之一，加一是防止gap<= 3時gap = gap / 3 = 0的發(fā)生，導致希爾增量最后不為1，無法完成插入排序。到目前為止業(yè)內(nèi)對于兩個大佬的方法依然是看法不一，都沒有比出個上下來

? 我們目前使用的則是Knuth提出的除三法獲得希爾增量來演示

三、代碼實現(xiàn) 1. 代碼實現(xiàn)思路

? 希爾排序的代碼實現(xiàn)比較魔幻，由于我們講解的希爾排序的思路是將分組進行直接插入排序，就導致我們?nèi)菀桩a(chǎn)生疑惑，是不是分多少組就調用多少次插入排序的代碼呢，那這代碼量不就隨著增量的變化而變化了，但是動態(tài)代碼這個概念聽著就讓人倍感稀奇。所以我們僅用一次遍歷數(shù)組的方式就巧妙對每個分組完成單趟排序，不需要對代碼做那樣鬼畜的操作

1. 當我們以希爾增量開始遍歷時，由于一次跨gap訪問下一個數(shù)據(jù)，所以我們用i變量從0遍歷到size-gap-1處，即紅色箭頭處

2. 當i=0時，我們用end變量從后往前遍歷插入，將end+gap作為下一個數(shù)據(jù)的位置，此時end+gap數(shù)據(jù)大于end處數(shù)據(jù)，原地插入(不做插入)即可。（g箭頭指向end+gap處的數(shù)據(jù)）

3. 此時i++，end再次往前遍歷，找end+gap處數(shù)據(jù)該插入的位置，6依然大于3，不做插入

4. i接著向后遍歷，end變量找end+gap處數(shù)據(jù)該插入的位置，2依然大于4，不做插入

5. i還是遍歷，end變量向前找到end+gap處數(shù)據(jù)的插入位置，7比8小，end向前移動gap位，將該數(shù)據(jù)插入到此時的end+gap位置

6. i遍歷到下一個，此時end+gap為1，比6小，end向前移動gap位，將該數(shù)據(jù)插入到此時的end+gap位置
7. 此時end+gap為1，依然比end處的3小，end繼續(xù)減gap，在end+gap處繼續(xù)插入（此時end< 0，但是我們以end+gap作為插入位置，所以不會造成數(shù)組越界）

7. 此時i不用動了，剛好到size-gap-1處，循環(huán)結束，第一趟遍歷就結束了

8. 然后縮小增量gap = gap / 3 + 1，gap = 1，接著插入排序，直到排序完成

? 這個過程相當于對每個分組按照一個固定順序輪流插入排序，并且它們是以一個元素為單位同時進行的，而不是先將某個分組插入排序完再下一個分組。

2. 實現(xiàn)代碼

void ShellSort(int* arr, int size)
{int gap = size;
    while (gap >1)
    {gap = gap / 3 + 1;	//調整希爾增量
        int i = 0;
        for (i = 0; i< size - gap; i++)	//從0遍歷到size-gap-1
        {int end = i;
            int temp = arr[end + gap];
            while (end >= 0)
            {if (arr[end] >temp)
                {arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {break;
                }
            }
            arr[end + gap] = temp;	//以 end+gap 作為插入位置
        }
    }
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前名稱：【排序算法】希爾排序（C語言）-創(chuàng)新互聯(lián)
文章鏈接：http://fisionsoft.com.cn/article/piiod.html