1.2.常見排序應用：

而排序其實在我們生活中運用十分廣泛，例如在購物網站上選購一個電腦，可以通過綜合、銷量、評論數、新品價格來排序，如果對價格有需求，也可以按照價格升序，或者降序來排序，通過這種方式來買到心儀的商品。

不難發(fā)現，在我們的日常生活中排序算的使用隨處可見，充斥著我們的各項生產活動，我們的考試排名、績效考核、綜測排名，包括CSDN的各種排名都廣泛的使用到了許多種不盡相同的排序算法。

而究其根本，這些都需要排序算法來實現。那么在編程中有什么排序算法，它們的性能如何？如何模擬實現這些算法？

接下來的幾篇博客中，我們會依次學習常見的排序算法，并進行對比，以便于我們更好的理解這些算法的使用方式、使用條件與適用場景等等。

2.常見的排序算法：

最常用的排序算法可以分為四大類：插入排序、選擇排序、交換排序與歸并排序。插入排序的代表算法有直接插入排序與希爾排序；選擇排序的排序算法代表是選擇排序與堆排序；交換排序中我們要熟識冒泡排序與快速排序；歸并排序則主要是以歸并排序算法為主，及一些由歸并思想衍生出的排序算法。

下圖是常見八大排序的比較：

2、直接插入排序

2.1 排序思路

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個 已經排好序的有序序列 中，直到所有的記錄插入完為止，得到一個新的有序序列 。

我們的撲克牌就使用了插入排序的思想：

比如拿到牌之后，我們都會理牌，那么通常就會按照大小順序，將牌理成整體有序，或者局部有序。

其實插入排序的過程就可以想象成之前我們學習 順序表 的尾插 ，我們假定序列 array[] 只有 1 個數。假定每次都是插入一個元素，且插入的元素需要將這個 ”順序表“ 構成有序，如果插入元素array[i]<arr[i?1] ，那么就至少需要向前調整 1次；如果array[i]≥array[i?1] 那么就 直接插入在 i下標處 即可。

動圖演示插入排序過程：

2.2 代碼實現

對于 單趟插入排序 ，假設 end 是上一次排序的最后一個位置，那么本次需要排序的元素為 tmp=a[end+1] 。

之后通過一個循環(huán)，如果a[end]>tmp ，說明 tmp 插入的位置在前面，所以把a[end+1]=a[end] ，將元素往后移 1 格，并將 end?? ，將索引向前調整；如果 a[end]<=tmp ，說明tmp 在當前位置：end+1 就可以直接插入，停止循環(huán)。

最后 end 停下來的位置永遠是插入位置的前一個位置 ，比如看下圖：

這是單趟，那么完整的就是n?1 趟，因為第一個元素是不用排的，第一趟其實就是排的序列的第二個元素了。每趟最終插入的位置為 end + 1 ，注意防止越界。

完整的多趟 實現步驟：
1.從第一個元素開始，該元素可以認為已經被排序。
2.取下一個元素作為 tmp，從已排序的元素序列從后向前掃描。
3.如果該元素大于 tmp，則將該元素移到下一位。
4.重復步驟 3，直到找到已排序元素中小于或等于 tmp 的元素。
5.將 temp 插入到該元素的后面，如果已排序所有元素都大于 tmp，則將 tmp 插入到下標為 0 的位置。
重復步驟 2 ~ 5，直至完成排序。

void InserSort(int* a, int n)
{
	//多趟控制
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//單趟控制
		int end = i ;
		int temp = a[end + 1];
		while (end >= 0)
		{
			//目標數小于其它數時，其它數就往后挪；大于則插入
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	//代碼執(zhí)行到此有兩種情況:
	//1.待插入元素找到應插入位置（break跳出循環(huán)到此）
	//2.待插入元素比當前有序序列中的所有元素都?。╳hile循環(huán)結束后到此）
	}
}

2.3 特性及復雜度

插入排序的最壞的情況為原始序列為降序 。此時，時間復雜度最壞，為O(N^2)。
如果目的是升序，序列也正好是升序的話，為最好情況，這時時間復雜度為O(N) 。

取其最壞，最終時間復雜度：O(N^2)
插入排序并沒有開辟額外空間，所以 空間復雜度：O(1)

特性：元素集合越接近有序，直接插入排序算法的時間效率越高。
時間復雜度：O(N^2) 。
空間復雜度：O(1) 。
穩(wěn)定性：穩(wěn)定。

3、希爾排序

3.1 排序思路

希爾排序也屬于插入排序，但是和直接插入排序又略微不同。

概念：希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把所有待排序記錄記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，即所有記錄在統(tǒng)一組內排好序。

簡單來說，意思是取一個整數，作為 間距gap ，對于每個元素，與其間隔為gap 的元素分成一個組，對每組排序 。不斷調整gap，對每組進行不斷排序，在 gap調整到 1 后進行插入排序，就可以將數據排成有序。而按照間距gap分組并排序被稱為 預排序 。

所以可以歸納希爾排序的步驟就是 兩點 ：

1. 預排序 -目標：讓數組接近有序（分組插排）
2. 直接插入排序

比如，一次完整希爾排序 就像下圖：

3.2 代碼實現

希爾排序屬于插入排序，而它的思想其實是和直接插入排序差不多的，因為最后一次希爾排序為插入排序。希爾排序無非就是多了幾組預排序的過程。所以它的代碼和直接插入排序十分相似。

對于插入排序，我們其實就可以看做是 gap = 1的希爾排序，那么把插入排序一些數據做一下替換，就得出了單組希爾排序 ：

// 對于一組
for (int i = 0; i < n - gap; i += gap)
{
    // 對于單個元素
    int end = i;
    int tmp = a[end + gap];
    while (end >= 0)
    {
        if (tmp < a[end])
        {
            a[end + gap] = a[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    a[end + gap] = tmp;
}

這里的gap不僅是每組中元素的間距，也是組數。上面代碼只完成了單組，對于完整的一組需要在外面套上一層循環(huán)，需要循環(huán)gap次：

for (int j = 0; j < gap ;j++) 
{
	for (int i = j; i < n - gap; i += gap)
    {
        // ...
    }
}

我們發(fā)現，只需要把之前的挪動 1 位看成挪動 gap 位。

注意 對單組進行排序時的結束條件i < n - gap ，這里結束條件是這個的原因為最后一組的最后一個元素下標為 n - gap - 1 ，當元素進行插入時，不能越界。

但這樣寫，就套了 三層循環(huán) 了，看起來比較繁瑣，我們可以做出一些調整，上方代碼為排 gap 組，每次排一組。我們可以改進為gap 組并排 ：

for (int i = 0; i < n - gap; i++) // 注意這里從 i+= gap 變?yōu)?i++
{
    int end = i;
    int tmp = a[end + gap];

    while (end >= 0)
    {
        if (tmp < a[end])
        {
            a[end + gap] = a[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }

    a[end + gap] = tmp;
}

這里就只有 兩層循環(huán) 了，代碼更加簡潔，唯一改變的是i+=gap 變?yōu)閕++

這里就相當于，每一次都是排其他組的數據，舉個例子：當前 i = 0 ，那么此刻排的就是第一組，之后i++ ，i=1 ，那么此刻就是排的第二組 … 當循環(huán)結束，這gap 組數據也就都被排好了。這就是gap 組并排。

而 希爾排序的預排序的 gap 越大時，那么對于單組中的數據就可以更快地到后面(挪動間距為gap)，但這時的數據并不接近有序；而 gap 越小時，數據跳動越慢，但是越來越接近有序(比如插入排序) 。綜合這兩點，所以我們一般進行希爾排序時，gap 是動態(tài)變化的，gap 的初值一般為數組長度 。之后每次除以一半或者除以三分之一。

比如每次除以三分之一：

while (gap > 1)//gap=1 已經排過了
{
    gap = gap / 3 + 1; // 或 gap /= 2;
    // gap 組并排
    for (int i = 0; i < n - gap; i++)
    {
        int end = i;
        int tmp = a[end + gap];

        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + gap] = a[end];
                end -= gap;
            }
            else
            {
                break;
            }
        }
        a[end + gap] = tmp;
    }
}

分析：

這里調整是用的gap=gap/3+1，為什么在這邊+1 呢？原因是希爾排序最后 1 次為插入排序，所以最后 1 次gap=1 ，如果 gap 初值為 8，如果每次僅僅讓 gap/=3 ，由于c語言中 / 是下取整，那么每次gap 就為 8 2 0 ，最后 1次為 0 ，無法完成希爾排序，所以要加上一個 1 ，這樣就可以保證最后 1 次 gap=1 。

但是如果每次除以2的情況就不需要，因為每gap/=2 最終結果必定等于 1 ，可以通過舉例子證明。

3.3 特性及復雜度

數據被分為 gap 組，每組有 N/gap 個數據。對于單組，最壞的挪動次數就是1+2+3+…+N/gap?1 ，是公差為 1 的等差數列。

一共有gap 組，那么對于一次預排序的總次數就為(1+2+3+…+N/gap?1)×gap ，但是這里gap 是不確定的。那對于每次預排序的時間復雜度，該怎么計算?

1.首先，根據代碼分析
如果gap 每次除以 3 ，那么就大約進行 N / 3 / 3 / 3… / 3 = log ₃ N次；
如果gap 每次除以 2 ，那么就大約進行 N / 2 / 2 / 2… / 2 = log ₂N 次；

2.其次，假設gap 每次除以 3 ，一開始 N 很大，gap=N/3+1 ，將當前 gap 的取值帶入上方對于一次預排序的次數的公式中，通過極限的思想， ( 1 + 2 + 3 + . . . + $\frac{N}{(N/3+1)}$ ? 1 ) × ( N / 3 + 1 ) ≈ N ，那么起始處， 預排總次數約為 N

快結束時，gap 很小，本應該是N^2，但因為此刻由于預排序的作用 ，數組幾乎有序，幾乎不需要排序，這時次數也約為 N

而中間的計算結果需要的數學知識比較難，所以暫時先就將起始兩次的結果作為每次預排序的結果，時間復雜度為 O(N) 。

3.那么綜合起來，實際上希爾排序的時間復雜度大約在 [ log ₃N ? N , log₂N ? N ]
?
這個量級之間 ，和我們之前學習過的堆排序的時間復雜度相近。

但是這只是我們的一些計算推導，實際上希爾排序真正的時間復雜度很難計算，上面的計算只是簡單推導而已，里面其實涉及到了很多數學知識，所以我們參考一下一些著名的數據結構書籍中對于希爾排序時間復雜度的分析：

《數據結構(C語言版)》— 嚴蔚敏：

《數據結構-用面相對象方法與C++描述》— 殷人昆

而gap 是按照Knuth 大佬提出的方式取值的，Knuth大佬進行了大量的試驗統(tǒng)計，得出最接近的結論，希爾排序的最終時間復雜度為 O(N^1.3)左右。但如果有一天能找到最佳的gap，說不定快速排序的位置就被希爾取代了(bushi)

而空間復雜度就很簡單了，并沒有開辟額外的空間，所以空間復雜度為 O(1) 。

特性：希爾排序是對直接插入排序的優(yōu)化。
當 增量 > 1時都是預排序，目的是讓數組更接近于有序。當增量為 1 時，數組已經接近有序了，再進行排序就能提高算法執(zhí)行的時間效率。
時間復雜度：O(N^1.3) 。
空間復雜度：O(1) 。
穩(wěn)定性：不穩(wěn)定。

4.總結：

今天我們認識并學習了排序算法的相關概念，并且具體學習了插入排序算法中的直接插入排序和希爾排序。下一篇博客，我們將繼續(xù)學習交換排序中的直接選擇排序和堆排序。希望我的文章和講解能對大家的學習提供一些幫助。

當然，本文仍有許多不足之處，歡迎各位小伙伴們隨時私信交流、批評指正！我們下期見~

文章來源地址http://www.zghlxwxcb.cn/news/detail-419919.html

到了這里，關于【排序算法】排序算法介紹及插入排序 ( 直接插入排序 && 希爾排序 )的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！