歸並演算法優點

『壹』 歸並排序演算法

兩種歸並排序演算法的實現：二路歸並排序和基本歸並排序（虛擬消除遞歸的二路歸並排序）
#define ARRAY_SIZE 1024

int B[1024]; //使用一個全局變數，避免歸並排序中每次都重新申請和釋放空間造成的開銷

template <typename T>
void Merge(T A[], int l, int m, int h)
{
int i = l;
int j = m+1;
int k = 0;

while(i<=m&&j<=h)
{
if(A[i]<A[j])
{
B[k++] = A[i];
i++;
}
else
{
B[k++] = A[j];
j++;
}
}

while(i<=m)
{
B[k++] = A[i++];
}

while(j<=h)
{
B[k++] = A[j++];
}

for(i=l; i<=h; i++)
{
A[i] = B[i-l];
}
}

//二路歸並排序的實現

template <typename T>
void MergeSort(T a[], int l, int h)
{
int m = (h+l)/2;
if(l>=h)
{
return;
}

if(l+1==h)
{
if(a[l]>a[h])
{
std::swap(a[l], a[h]);
}

return;
}

MergeSort(a, l, m);
MergeSort(a, m+1, h);
Merge(a, l, m, h);
}

//將a經過步長s歸並到b中，n表示數組的大小
template <typename T>
void Merge2(T a[], T b[], int s, int n)
{
int m = 0;

//從頭至尾按照步長s進行相鄰數據的合並
for(int i=0; i<n; i+=2*s)
{
int j = i; //合並的第一組數的起始位置
int k = i+s; //合並的第二組數的起始位置
int jE = i+s; //合並的第一組數的起始位置
int kE = i+2*s; //合並的第二組數的起始位置

while((j<jE)&&(k<kE)&&j<n && k<n)
{
if(a[j]<a[k])
{
b[m++] = a[j];
j++;
}
else
{
b[m++] = a[k];
k++;
}
}

while((j<jE)&&(j<n))
{
b[m++] = a[j++];
}

while((k<kE)&&(k<n))
{
b[m++] = a[k++];
}
}
}

//基本歸並排序，虛擬消除遞歸
template <typename T>
void MergeSort2(T a[], int n)
{
int s = 1; //merge 的步長
T* b = new T[n];

while(s<n)
{
Merge2(a, b, s, n); //由a合並到b
s += s;

Merge2(b, a, s, n); //由b合並到a
s += s;
}

delete[] b;
}

//使用如下代碼在VS2005中可以對兩種歸並排序進行性能比較，

//基本歸並排序的時間性能稍微好一點，基本歸並排序直接對數據按步長Merge，

//而二路歸並排序需要將數據先不斷的分層，到為一個或者兩個元素時再進行Merge

void main()
{
int * p = new int[ARRAY_SIZE];
int i = 0;

for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort(p, 0, ARRAY_SIZE-1);

for(i=0; i<ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort2(p, ARRAY_SIZE);

delete[] p;
}

『貳』 什麼叫歸並演算法

合並排序（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;
}

『叄』 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；

學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。

排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。

2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。

排序的穩定性

當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。

排序方法的分類

1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。

2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

排序演算法分析

1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。

2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。

3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度

（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。

（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。

文件的順序存儲結構表示

#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時間將排序分為四類：

（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；

（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
如桶、箱和基數排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

影響排序效果的因素

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。

4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

『肆』 簡述各種排序演算法的優缺點

一、冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大於a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數 據元素排完。
選擇排序是不穩定的排序方法。
n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1 趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1 個記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個數增加1 個的新有序區和記錄個數減少1 個的新無序區。
③第i 趟排序
第i 趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區中選出關鍵字最 小的記錄 R[k]，將它與無序區的第1 個記錄R 交換，使R[1..i]和R 分別變為記錄個數增加1 個的新有序區和記錄個數減少 1 個的新無序區。
這樣，n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果。
優點：移動數據的次數已知（n-1 次）；
缺點：比較次數多。

三、插入排序
已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。 首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大於a[2]，則繼續跳過，直 到b[1]小於a 數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1 的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決 這個問題。

四、縮小增量排序
由希爾在1959 年提出，又稱希爾排序(shell 排序)。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n 不大時，插入 排序的效果很好。首先取一增 量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……="" 列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操="" 作，直到d="1。"
優點：快，數據移動少；=""
缺點：不穩定，d="" 的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。=""

五、快速排序=""
快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。
="" 已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]="" 作為基準。比較a[x]與其它數據並="" 排序，使a[x]排在數據的第k="" 位，並且使a[1]~a[k-1]中的每一個數="" 據a[x]，然後采 用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。

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

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（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 中即可。

『陸』 在快速排序、堆排序、歸並排序中，什麼排序是穩定的

歸並排序是穩定的排序演算法。

歸並排序的穩定性分析：

歸並排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素或者2個序列，然後把各個有序的段序列合並成一個有序的長序列，不斷合並直到原序列全部排好序。

可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等，沒有外部干擾，將不會破壞穩定性。

那麼，在短的有序序列合並的過程中，穩定性是沒有受到破壞的，合並過程中如果兩個當前元素相等時，把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩定性。所以，歸並排序也是穩定的排序演算法。

(6)歸並演算法優點擴展閱讀：

演算法穩定性的判斷方法：

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

對於不穩定的排序演算法，只要舉出一個實例，即可說明它的不穩定性；而對於穩定的排序演算法，必須對演算法進行分析從而得到穩定的特性。

需要注意的是，排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。

比如，快速排序原本是不穩定的排序方法，但若待排序記錄中只有一組具有相同關鍵碼的記錄，而選擇的軸值恰好是這組相同關鍵碼中的一個，此時的快速排序就是穩定的。

參考資料來源：網路-排序演算法穩定性

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

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

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

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

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

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

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

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

『捌』 java里,幾種排序方法各有什麼優缺點

一、冒泡排序

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較 a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對 a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。

優點：穩定；

缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序

冒泡排序的改進版。

每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。

選擇排序是不穩定的排序方法。

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

①初始狀態：無序區為R[1..n]，有序區為空。

②第1趟排序

在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

③第i趟排序

第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n- 1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

優點：移動數據的次數已知（n-1次）；

缺點：比較次數多。

三、插入排序

已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）

優點：穩定，快；

缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決這個問題。

三、縮小增量排序

由希爾在1959年提出，又稱希爾排序(shell排序)。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操作，直到d=1。

優點：快，數據移動少；

缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。

四、快速排序

快速排序是目前已知的最快的排序方法。

已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據 a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。

優點：極快，數據移動少；

缺點：不穩定。

五、箱排序

已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……a[n]，接著循環n次，每次x[a]++.

優點：快，效率達到O(1)

缺點：數據范圍必須為正整數並且比較小

六、歸並排序

歸並排序是多次將兩個或兩個以上的有序表合並成一個新的有序表。最簡單的歸並是直接將兩個有序的子表合並成一個有序的表。

歸並排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息盡量按輸入的順序排列時很重要.這也是它比快速排序優勢的地方.

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

歸並排序演算法是建立在歸並操作上的一種有效，穩定的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。歸並操作，也叫歸並演算法，指的是將兩個順序序列合並成一個順序序列的方法。

將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

演算法比較：

歸並排序是穩定的排序．即相等的元素的順序不會改變．如輸入記錄1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字）時輸出的1(1) 2(3) 2(4) 3(2) 5(5)中的2和2是按輸入的順序。

這對要排序數據包含多個信息而要按其中的某一個信息排序，要求其它信息盡量按輸入的順序排列時很重要。歸並排序的比較次數小於快速排序的比較次數，移動次數一般多於快速排序的移動次數。

速度僅次於快速排序，為穩定排序演算法，一般用於對總體無序，但是各子項相對有序的數列，應用見2011年普及復賽第3題「瑞士輪」的標程。

以上內容參考：網路-歸並排序