合並排序的演算法思想

『壹』 歸並排序的演算法原理是什麼

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，歸並排序將兩個已排序的表合並成一個表。
歸並排序基本原理

通過對若干個有序結點序列的歸並來實現排序。
所謂歸並是指將若干個已排好序的部分合並成一個有序的部分。

歸並排序基本思想

設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：array[low..m]，array[m + 1..high]，先將它們合並到一個局部的暫存序列 temp (相當於輸出序列)中，待合並完成後將 temp 復制回 array[low..high]中，從而完成排序。

在具體的合並過程中，設置 i，j 和 p 三個指針，其初值分別指向這三個記錄區的起始位置。合並時依次比較 array[i] 和 array[j] 的關鍵字，取關鍵字較小（或較大）的記錄復制到 temp[p] 中，然後將被復制記錄的指針 i 或 j 加 1，以及指向復制位置的指針 p加 1。重復這一過程直至兩個輸入的子序列有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子序列中剩餘記錄依次復制到 array 中即可。

『貳』 數據結構--歸並排序與基數排序

一、歸並排序
歸並排序（MERGE-SORT）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。將兩個或以上的有序表組合成一個新的有序表。
1、2-路歸並排序
初始序列含有n個記錄，可看成n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到[n/2]個長度為2或1的有序子序列，再兩兩歸並，如此重復，直至得到一個長度為n的有序序列為止。
2、舉例

上圖中的最後一次合並，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合並為最終序列[1,2,3,4,5,6,7,8]，實現步驟：

Tips：
排序演算法的穩定性：保證排序前2個相等的數，在序列中的前後位置順序和排序後它們兩個的前後位置順序相同。例如，Ai = Aj，Ai排序前位於Aj的前面，排序後Ai還位於Aj的前面。
穩定性的好處：排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就 是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。
排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。
例如，對於如下冒泡排序演算法，原本是穩定的排序演算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩定的演算法。

堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。

一、基數排序
基數排序是一種藉助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。
1、什麼是多關鍵字
已知撲克牌中52張牌面的次序關系為：

1、最高位優先於最低位優先

假設有n個記錄的序列{R ₁ ，R ₂ ，...R _n }，且每個記錄R _i 中含有d個關鍵字(K _i ¹ ，K _i ² ，...，K _i ^d )，序列{R ₁ ，R ₂ ，...R _n }對關鍵字(K ¹ ，K ² ，...，K ^d )有序是指：對於序列中任意兩個記錄R _i 和R _j (1 <= i < j <= n)都滿足下列有序關系：(K _i ¹ ，K _i ² ，...，K _i ^d )<(K _j ¹ ，K _j ² ，...，K _j ^d )，其中K ¹ 稱為最高位關鍵字，K ^d 稱為最低位關鍵字。

實現多關鍵字排序的方法：
A、先對最高位關鍵字K ¹ 進行排序，間序列分成若乾子序列，每個子序列中的記錄都具有相同的K ¹ 值，然後分別對每個子序列對關鍵字K ² 進行排序，按K ² 值不同再分成若干更小的子序列，依次重復，直到對K ^d-1 進行排序後得到的每一子序列中的記錄都具有相同的關鍵字(K ¹ ，K ² ，...，K ^d-1 )，而後每個子序列分別對K ^d 進行排序，最後將所要子序列依次連接在一起成為一個有序序列，這種方法為「最高位優先(MSD)」
B、先從最低位關鍵字K ^d 進行排序，在對高一位的關鍵字K ^d-1 進行排序，依次重復，直至對K ¹ 進行排序後便成為一個有序序列。這種方法稱為「最低位優先(LSD)」。

三、內部排序方法的比較

結論：
1、表中的「簡單排序」指：除希爾排序外的所有插入排序，冒泡排序和簡單選擇排序，其中之間插入排序最簡單，當序列中的記錄「基本有序」或n值較小時，它是最佳的排序方法，因此常將他和其他排序方法（快排，歸並排序）結合在一起使用。
2、從平均時間性能看，快排最省時間，但他在最壞情況下的時間性能不如堆排序和歸並排序。在n較大，歸並排序所需時間比堆排序少，但所需的輔助存儲量最多。
3、基數排序適用於n值很大且關鍵字較小的序列。

『叄』 排序演算法總結

排序演算法是什麼?有多少種?排序演算法總結又是怎樣?以下是為您整理的排序演算法總結，供您參考!

【排序演算法總結】

排序演算法：一種能將一串數據依照特定的排序方式進行排列的一種演算法。

排序演算法性能：取決於時間和空間復雜度，其次還得考慮穩定性，及其適應的場景。

穩定性：讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序演算法是穩定的，當有倆個相等鍵值的記錄R和S，且原本的序列中R在S前，那麼排序後的列表中R應該也在S之前。

以下來總結常用的排序演算法，加深對排序的理解。

冒泡排序

原理

倆倆比較相鄰記錄的排序碼，若發生逆序，則交旅派配換;有倆種方式進行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到後邊。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。排序是穩定的，排序比較次數與初始序列無關，但交換次數與初始序列有關。

優化

若初始序列就是排序好的，對於冒泡排序仍然還要比較O(N^2)次，但無交換次數。可根據這個進行優化，設置一個flag，當在一趟序列中沒有發生交換，則該序列已排序好，但優化後排序的時間復雜度沒有發生量級的改變。

代碼

插入排序

原理

依次選擇一個待排序的數據，插入到前邊已排好序的序列中。

性能

時間復雜度為O(N^2)，空間復雜度為O(1)。演算法是穩定的，比較次數和交換次數都與初始序列有關。

優化

直接插入排序每次往前插入時，是按順序依次往前找，可在這里進行優化，往前找合適的插入位置時採用二分查找的方式，即折半插入。

折半插入排序相對直接插入排序而言：平均性能更快，時間復雜度降至O(NlogN)，排序是穩定的，但排序的比較次數與初始序列無關，總是需要foor(log(i))+1次排序比較。

使用場景

當數據基本有序時，採用插入排序可以明顯減少數據交換和數據移動次數，進而提升排序效率。

代碼

希爾排拆指序

原理

插入排序的改進版，是基於插入排序的以下倆點性質而提出的改進方法：

插入排序對幾乎已排好序的數據操作時，效率很高，可以達到線性排序的效率。

但插入排序在每次往前插入時只能將數據移動一位，效率比較低。

所以希爾排序的思想是：

先是取一個合適的gap

縮小間隔gap，例如去gap=ceil(gap/2)，重復上述子序列劃分和排序

直到，最後gap=1時，將所有元素放在同一個序列中進行插入排序為止。

性能

開始時，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點;其次，gap值逐漸變小後，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優點，能以近線性的速度排好序。

代碼

選擇排序

原理

每次從未排序的序列中找到最小值，記錄並最後存放到已排序序羨碰列的末尾

性能

時間復雜度為O(N^2)，空間復雜度為O(1)，排序是不穩定的(把最小值交換到已排序的末尾導致的)，每次都能確定一個元素所在的最終位置，比較次數與初始序列無關。

代碼

快速排序

原理

分而治之思想：

Divide：找到基準元素pivot，將數組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1…q]，左邊的元素都比基準小，右邊的元素都比基準大;

Conquer：對倆個劃分的數組進行遞歸排序;

Combine：因為基準的作用，使得倆個子數組就地有序，無需合並操作。

性能

快排的平均時間復雜度為O(NlogN)，空間復雜度為O(logN)，但最壞情況下，時間復雜度為O(N^2)，空間復雜度為O(N);且排序是不穩定的，但每次都能確定一個元素所在序列中的最終位置，復雜度與初始序列有關。

優化

當初始序列是非遞減序列時，快排性能下降到最壞情況，主要因為基準每次都是從最左邊取得，這時每次只能排好一個元素。

所以快排的優化思路如下：

優化基準，不每次都從左邊取，可以進行三路劃分，分別取最左邊，中間和最右邊的中間值，再交換到最左邊進行排序;或者進行隨機取得待排序數組中的某一個元素，再交換到最左邊，進行排序。

在規模較小情況下，採用直接插入排序

代碼

歸並排序

原理

分而治之思想：

Divide：將n個元素平均劃分為各含n/2個元素的子序列;

Conquer：遞歸的解決倆個規模為n/2的子問題;

Combine：合並倆個已排序的子序列。

性能

時間復雜度總是為O(NlogN)，空間復雜度也總為為O(N)，演算法與初始序列無關，排序是穩定的。

優化

優化思路：

在規模較小時，合並排序可採用直接插入;

在寫法上，可以在生成輔助數組時，倆頭小，中間大，這時不需要再在後邊加倆個while循環進行判斷，只需一次比完。

代碼

堆排序

原理

堆的性質：

是一棵完全二叉樹

每個節點的值都大於或等於其子節點的值，為最大堆;反之為最小堆。

堆排序思想：

將待排序的序列構造成一個最大堆，此時序列的最大值為根節點

依次將根節點與待排序序列的最後一個元素交換

再維護從根節點到該元素的前一個節點為最大堆，如此往復，最終得到一個遞增序列

性能

時間復雜度為O(NlogN)，空間復雜度為O(1)，因為利用的排序空間仍然是初始的序列，並未開辟新空間。演算法是不穩定的，與初始序列無關。

使用場景

想知道最大值或最小值時，比如優先順序隊列，作業調度等場景。

代碼

計數排序

原理

先把每個元素的出現次數算出來，然後算出該元素所在最終排好序列中的絕對位置(最終位置)，再依次把初始序列中的元素，根據該元素所在最終的絕對位置移到排序數組中。

性能

時間復雜度為O(N+K)，空間復雜度為O(N+K)，演算法是穩定的，與初始序列無關，不需要進行比較就能排好序的演算法。

使用場景

演算法只能使用在已知序列中的元素在0-k之間，且要求排序的復雜度在線性效率上。

代碼

桶排序

原理

根據待排序列元素的大小范圍，均勻獨立的劃分M個桶

將N個輸入元素分布到各個桶中去

再對各個桶中的元素進行排序

此時再按次序把各桶中的元素列出來即是已排序好的。

性能

時間復雜度為O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空間復雜度為O(N+M)，演算法是穩定的，且與初始序列無關。

使用場景

演算法思想和散列中的開散列法差不多，當沖突時放入同一個桶中;可應用於數據量分布比較均勻，或比較側重於區間數量時。

基數排序

原理

對於有d個關鍵字時，可以分別按關鍵字進行排序。有倆種方法：

MSD：先從高位開始進行排序，在每個關鍵字上，可採用計數排序

LSD：先從低位開始進行排序，在每個關鍵字上，可採用桶排序

性能

時間復雜度為O(d*(N+K))，空間復雜度為O(N+K)。

總結

以上排序演算法的時間、空間與穩定性的總結如下：

『肆』 歸並排序演算法是什麼

歸並排序（Merge Sort）是建立在歸並操作上的一種有效，穩定的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

歸並操作的工作原理如下：

第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列。

第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置。

第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置。

重復步驟3直到某一指針超出序列尾。

將另一序列剩下的所有元素直接復制到合並序列尾。

『伍』 歸並排序演算法：用兩路歸並演算法，實現N個無素的排序

合並排序（MERGE SORT）是又一類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成一個新的有序數據序列，因此它又叫歸並演算法。它的基本思想就是假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。

例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那麼採用歸並排序演算法的操作過程如圖7所示：

初始值 [49] [38] [65] [97] [76] [13] [27]

看成由長度為1的7個子序列組成

第一次合並之後 [38 49] [65 97] [13 76] [27]

看成由長度為1或2的4個子序列組成

第二次合並之後 [38 49 65 97] [13 27 76]

看成由長度為4或3的2個子序列組成

第三次合並之後 [13 27 38 49 65 76 97]

合並演算法的核心操作就是將一維數組中前後相鄰的兩個兩個有序序列合並成一個有序序列。合並演算法也可以採用遞歸演算法來實現，形式上較為簡單,但實用性很差。合並演算法的合並次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這一規律,當有N個子序列時可以推斷出合並的次數是X(2 >=N,符合此條件的最小那個X)。
其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)

歸並演算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}

long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}