C語言常用排序算法
時間：2018-01-08 來源：未知
概述排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。
我們這里說說八大排序就是內部排序。
當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序：是目前基于比較的內部排序中被認為是好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間短;
1. 插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。
直接插入排序示例：
如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。
算法的實現：
//插入排序效率：
時間復雜度：O(n^2).
其他的插入排序有二分插入排序，2-路插入排序。
2. 插入排序—希爾排序(Shell`s Sort)
希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序。希爾排序是非穩定排序算法。
基本思想：
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序;隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
操作方法：
排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序;然后取d2<d1，重復上述分組和排序操作;直至di=1，即所有記錄放進一個組中排序為止。
算法實現：
我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數的個數
即：先將要排序的一組記錄按某個增量d(n/2,n為要排序數的個數)分成若干組子序列，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量(d/2)對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，后使用直接插入排序完成排序。
//shell排序
void Shell_Sort(int *list,int count)
{
int i,j;
int temp;
int num= count;
do
{
num= num/2;
for(i = num;i<count;i++)
{
if(list[i]<list[i-num])
{
temp = list[i];
for(j=i-num;j>=0&&list[j]>temp;j-=num)
{
list[j+num] = list[j];
}
list[j+num] = temp;
}
}
}while(num>1);
}
希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于增量因子序列d的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1 外沒有公因子，且后一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法。希爾排序時間復雜度的下界是n*log2n，因此中等大小規模表現良好。
3. 選擇排序—簡單選擇排序(Simple Selection Sort)
基本思想：
在要排序的一組數中，選出小(或者大)的一個數與第1個位置的數交換;然后在剩下的數當中再找小(或者大)的與第2個位置的數交換，依次類推，直到第n-1個元素(倒數第二個數)和第n個元素(后一個數)比較為止。
簡單選擇排序的示例：
進行比較操作的時間復雜度為O(n^2)，進行移動操作的時間復雜度為O(n)。簡單選擇排序是不穩定排序。
操作方法：
第一趟，從n 個記錄中找出關鍵碼小的記錄與第一個記錄交換;
第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼小的記錄與第二個記錄交換;
以此類推.....
第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼小的記錄與第i 個記錄交換，
直到整個序列按關鍵碼有序。
算法實現：
//選擇排序
void Select_Sort(int *list,int count)
{
int min,i,j;
for(i=0;i<count;i++)
{
min = i;
for(j=i+1;j<count;j++)
{
if(list[min]>list[j])
{
min = j;
}
}
if(min!=i)
{
swap(list[i],list[min]);
}
}
}
簡單選擇排序的改進——二元選擇排序
簡單選擇排序，每趟循環只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環確定兩個元素(當前趟大和小記錄)的位置,從而減少排序所需的循環次數。改進后對n個數據進行排序，多只需進行[n/2]趟循環即可。
4. 選擇排序—堆排序(Heap Sort)
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。
基本思想：
堆的定義如下：具有n個元素的序列(k1,k2,...,kn),當且僅當滿足
時稱之為堆。由堆的定義可以看出，堆頂元素(即第一個元素)必為小項(小頂堆)。
若以一維數組存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大于(或不小于)其子女的值，根結點(堆頂元素)的值是小(或大)的。如：
(a)大頂堆序列：(96，83，27，38，11，09)
(b)小頂堆序列：(12，36，24，85，47，30，53，91)
初始時把要排序的n個數的序列看作是一棵順序存儲的二叉樹(一維數組存儲二叉樹)，調整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中小(或大)的元素，這時堆的根節點的數小(或者大)。然后對前面(n-1)個元素重新調整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節點的堆，并對它們作交換，后得到有n個節點的有序序列。稱這個過程為堆排序。
因此，實現堆排序需解決兩個問題：
1. 如何將n 個待排序的數建成堆;
2. 輸出堆頂元素后，怎樣調整剩余n-1 個元素，使其成為一個新堆。
首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調整過程。
調整小頂堆的方法：
1)設有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂((后一個元素與堆頂進行交換)，堆被破壞，其原因僅是根結點不滿足堆的性質。
2)將根結點與左、右子樹中較小元素的進行交換。
3)若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結點不滿足堆的性質，則重復方法 (2).
4)若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結點不滿足堆的性質。則重復方法 (2).
5)繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。
稱這個自根結點到葉子結點的調整過程為篩選。如圖：
再討論對n 個元素初始建堆的過程。
建堆方法：對初始序列建堆的過程，就是一個反復進行篩選的過程。
1)n 個結點的完全二叉樹，則后一個結點是第個結點的子樹。
2)篩選從第個結點為根的子樹開始，該子樹成為堆。
3)之后向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。
如圖建堆初始過程：無序序列：(49，38，65，97，76，13，27，49)
算法的實現：
從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的后一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。
//調整為一個堆
void Heap_Adjust(int *list,int s,int m)
{
int temp = list[s];
for(int j=2*s+1;j<=m;j = 2*j+1)
{
if(list[j]<list[j+1]&&j<m)
{
j++;
}
if(temp>list[j])
break;
list[s] = list[j];
s = j;
}
list[s] = temp;
}
//堆排序
void Heap_Sort(int *list,int len)
{
//創建一個大頂堆
for(int s = len/2-1;s>=0;s--)
{
Heap_Adjust(list,s,len-1);
}
//排序
for(int i = len-1;i >= 1;i--)
{
swap(list[0],list[i]);
Heap_Adjust(list,0,i-1);
}
}
分析:
設樹深度為k，。從根到葉的篩選，元素比較次數至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過程中的篩選次數不超過下式：
而建堆時的比較次數不超過4n 次，因此堆排序壞情況下，時間復雜度也為：O(nlogn )。
由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩定的排序方法。
5. 交換排序—冒泡排序(Bubble Sort)
基本思想：
在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。
冒泡排序的示例：
算法的實現：
//冒泡排序
void Bubble_Sort(int *list,int count)
{
int flag = true;
int i = 0,j = 0;
for(i=0;i<=count&&flag;i++)
{
flag = false;
for(j=count -1;j>=i;j--)
{
if(list[j]<list[j-1])
{
swap(list[j],list[j-1]);
flag = true;
}
}
}
}
冒泡排序算法的改進
對冒泡排序常見的改進方法是加入一標志性變量exchange，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換，則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程。本文再提供以下兩種改進算法：
1.設置一標志性變量pos,用于記錄每趟排序中后一次進行交換的位置。由于pos位置之后的記錄均已交換到位,故在進行下一趟排序時只要掃描到pos位置即可。
2.傳統冒泡排序中每一趟排序操作只能找到一個大值或小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個終值(大者和小者) , 從而使排序趟數幾乎減少了一半。
6. 交換排序—快速排序(Quick Sort)
基本思想：
一趟快速排序的算法是：
1)設置兩個變量i、j，排序開始的時候：i=0，j=N-1;
2)以第一個數組元素作為關鍵數據，賦值給key，即key=A[0];
3)從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換;
4)從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換;
5)重復第3、4步，直到i=j; (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束)。
(a)一趟排序的過程：
算法的實現：
//快速排序
int Partition(int *list,int low,int high)
{
int pivotKey;
pivotKey = list[low];
while(low<high)
{
while(low<high&&list[high]>=pivotKey)
{
high--;
}
swap(list[low],list[high]);
while(low<high&&list[low]<=pivotKey)
{
low++;
}
swap(list[low],list[high]);
}
return low;
}
void Qsort(int *list,int low,int high)
{
int pivot;
if(low<high)
{
pivot =Partition(list,low,high);
Qsort(list,low,pivot-1);
Qsort(list,pivot+1,high);
}
}
void Quick_Sort(int *list,int count)
{
Qsort(list,0,count-1);
}
分析：
快速排序是通常被認為在同數量級(O(nlog2n))的排序方法中平均性能好的。但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取基準記錄，即將排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。快速排序是一個不穩定的排序方法。
快速排序的改進
在本改進算法中,只對長度大于k的子序列遞歸調用快速排序,讓原序列基本有序，然后再對整個基本有序序列用插入排序算法排序。實踐證明，改進后的算法時間復雜度有所降低，且當k取值為 8 左右時,改進算法的性能佳。
7. 歸并排序(Merge Sort)
基本思想：
歸并(Merge)排序法是將兩個(或兩個以上)有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序示例：
合并方法：
設r[i…n]由兩個有序子表r[i…m]和r[m+1…n]組成，兩個子表長度分別為n-i +1、n-m。
1.j=m+1;k=i;i=i; //置兩個子表的起始下標及輔助數組的起始下標
2.若i>m 或j>n，轉⑷ //其中一個子表已合并完，比較選取結束
3.//選取r[i]和r[j]較小的存入輔助數組rf
如果r[i]<r[j]，rf[k]=r[i]; i++; k++; 轉⑵
否則，rf[k]=r[j]; j++; k++; 轉⑵
4.//將尚未處理完的子表中元素存入rf
如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空
如果j<=n , 將r[j…n] 存入rf[k…n] //后一子表非空
5.合并結束。
//歸并排序
//將兩個有序數組排序
void Merge(int *list,int start,int mid,int end)
{
const int len1 = mid -start +1;
const int len2 = end -mid;
const int len = end - start +1;
int i,j,k;
int * front = (int *)malloc(sizeof(int)*len1);
int * back = (int *)malloc(sizeof(int)*len2);
for(i=0;i<len1;i++)
front[i] = list[start+i];
for(j=0;j<len2;j++)
back[j] = list[mid+j+1];
for(i=0,j=0,k=start;i<len1&&j<len2&&k<end;k++)
{
if(front[i]<back[j])
{
list[k] = front[i];
i++;
}
else
{
list[k] = back[j];
j++;
}
}
while(i<len1)
{
list[k++] = front[i++];
}
while(j<len2)
{
list[k++] = back[j++];
}
}
void MSort(int *list,int start,int end)
{
if(start<end)
{
int mid = (start+end)/2;
MSort(list,0,mid);
MSort(list,mid+1,end);
Merge(list,start,mid,end);
}
}
void Merge_Sort(int *list,int count)
{
MSort(list,0,count-1);
}
8. 桶排序/基數排序(Radix Sort)
說基數排序之前，我們先說桶排序：
基本思想(桶排序)：
是將陣列分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序算法或是以遞回方式繼續使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間(Θ(n))。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數據分組，放在一個個的桶中，然后對每個桶里面的在進行排序。
例如要對大小為[1..1000]范圍內的n個整數A[1..n]排序
首先，可以把桶設為大小為10的范圍，具體而言，設集合B[1]存儲[1..10]的整數，集合B[2]存儲(10..20]的整數，……集合B[i]存儲((i-1)*10, i*10]的整數，i = 1,2,..100。總共有100個桶。
然后，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應的桶B[j]中。再對這100個桶中每個桶里的數字排序，這時可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。
后，依次輸出每個桶里面的數字，且每個桶中的數字從小到大輸出，這樣就得到所有數字排好序的一個序列了。
假設有n個數字，有m個桶，如果數字是平均分布的，則每個桶里面平均有n/m個數字。如果對每個桶中的數字采用快速排序，那么整個算法的復雜度是
O(n+ m * n/m*log(n/m)) = O(n + nlogn - nlogm)
從上式看出，當m接近n的時候，桶排序復雜度接近O(n)
當然，以上復雜度的計算是基于輸入的n個數字是平均分布這個假設的。這個假設是很強的，實際應用中效果并沒有這么好。如果所有的數字都落在同一個桶中，那就退化成一般的排序了。
前面說的幾大排序算法 ，大部分時間復雜度都是O(n2)，也有部分排序算法時間復雜度是O(nlogn)。而桶式排序卻能實現O(n)的時間復雜度。但桶排序的缺點是：
1)首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數組的空間開銷，一個存放待排序數組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數組就要至少m個空間。
2)其次待排序的元素都要在一定的范圍內等等。
桶式排序是一種分配排序。分配排序的特定是不需要進行關鍵碼的比較，但前提是要知道待排序列的一些具體情況。
分配排序的基本思想：說白了就是進行多次的桶式排序。
基數排序過程無須比較關鍵字，而是通過“分配”和“收集”過程來實現排序。它們的時間復雜度可達到線性階：O(n)。
實例:
撲克牌中52 張牌，可按花色和面值分成兩個字段，其大小關系為：
花色： 梅花< 方塊< 紅心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若對撲克牌按花色、面值進行升序排序，得到如下序列：
即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關系才由面值的大小確定。這就是多關鍵碼排序。
為得到排序結果，我們討論兩種排序方法。
方法1：先對花色排序，將其分為4 個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，后，將4 個組連接起來即可。
方法2：先按13 個面值給出13 個編號組(2 號，3 號，...，A 號)，將牌按面值依次放入對應的編號組，分成13 堆。再按花色給出4 個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應花色組，再將3 號組中牌取出分別放入對應花色組，……，這樣，4 個花色組中均按面值有序，然后，將4 個花色組依次連接起來即可。
設n 個元素的待排序列包含d 個關鍵碼{k1，k2，…，kd}，則稱序列對關鍵碼{k1，k2，…，kd}有序是指：對于序列中任兩個記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關系：
其中k1 稱為主位關鍵碼，kd 稱為次位關鍵碼 。
兩種多關鍵碼排序方法：
多關鍵碼排序按照從主位關鍵碼到次位關鍵碼或從次位到主位關鍵碼的順序逐次排序，分兩種方法：
高位優先(Most Significant Digit first)法，簡稱MSD 法：
1)先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關鍵碼k1 相等。
2)再對各組按k2 排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按次位關鍵碼kd 對各子組排序后。
3)再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。
低位優先(Least Significant Digit first)法，簡稱LSD 法：
1) 先從kd 開始排序，再對kd-1進行排序，依次重復，直到按k1排序分組分成小的子序列后。
2) 后將各個子序列連接起來，便可得到一個有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法。
基于LSD方法的鏈式基數排序的基本思想
“多關鍵字排序”的思想實現“單關鍵字排序”。對數字型或字符型的單關鍵字，可以看作由多個數位或多個字符構成的多關鍵字，此時可以采用“分配-收集”的方法進行排序，這一過程稱作基數排序法，其中每個數字或字符可能的取值個數稱為基數。比如，撲克牌的花色基數為4，面值基數為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞(分配)，再按此順序再疊放在一起(收集)，然后按面值的順序分成13摞(分配)，再按此順序疊放在一起(收集)，如此進行二次分配和收集即可將撲克牌排列有序。
基數排序:
是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次類推，直到高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序，分別收集，所以是穩定的。
算法實現：
#define MAX 20
#define BASE 10
void Radix_Sort(int *a, int n)
{
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i < n; i++)
{
if (a[i] > m)
{
m = a[i];
}
}
while (m / exp > 0)
{
int bucket[BASE] = { 0 };
for (i = 0; i < n; i++)
{
bucket[(a[i] / exp) % BASE]++;
}
for (i = 1; i < BASE; i++)
{
bucket[i] += bucket[i - 1];
}
for (i = n - 1; i >= 0; i--)
{
b[--bucket[(a[i] / exp) % BASE]] = a[i];
}
for (i = 0; i < n; i++)
{
a[i] = b[i];
}
exp *= BASE;
}
}
總結:
各種排序的穩定性，時間復雜度和空間復雜度總結：
我們比較時間復雜度函數的情況：
時間復雜度函數O(n)的增長情況
所以對n較大的排序記錄。一般的選擇都是時間復雜度為O(nlog2n)的排序方法。
時間復雜度來說：
(1)平方階(O(n2))排序
各類簡單排序:直接插入、直接選擇和冒泡排序;
(2)線性對數階(O(nlog2n))排序
快速排序、堆排序和歸并排序;
(3)O(n1+§))排序,§是介于0和1之間的常數。
希爾排序
(4)線性階(O(n))排序
基數排序，此外還有桶、箱排序。
說明：
當原表有序或基本有序時，直接插入排序和冒泡排序將大大減少比較次數和移動記錄的次數，時間復雜度可降至O(n);而快速排序則相反，當原表基本有序時，將蛻化為冒泡排序，時間復雜度提高為O(n2);原表是否有序，對簡單選擇排序、堆排序、歸并排序和基數排序的時間復雜度影響不大。
穩定性：
排序算法的穩定性:若待排序的序列中，存在多個具有相同關鍵字的記錄，經過排序， 這些記錄的相對次序保持不變，則稱該算法是穩定的;若經排序后，記錄的相對 次序發生了改變，則稱該算法是不穩定的。
穩定性的好處：排序算法如果是穩定的，那么從一個鍵上排序，然后再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩定，可以避免多余的比較;
穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序
不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序
選擇排序算法準則：
每種排序算法都各有優缺點。因此，在實用時需根據不同情況適當選用，甚至可以將多種方法結合起來使用。
選擇排序算法的依據
影響排序的因素有很多，平均時間復雜度低的算法并不一定就是優的。相反，有時平均時間復雜度高的算法可能更適合某些特殊情況。同時，選擇算法時還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下四點：
1.待排序的記錄數目n的大小;
2.記錄本身數據量的大小，也就是記錄中除關鍵字外的其他信息量的大小;
3.關鍵字的結構及其分布情況;
4.對排序穩定性的要求。
設待排序元素的個數為n.
1)當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
快速排序：是目前基于比較的內部排序中被認為是好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間短;
堆排序：如果內存空間允許且要求穩定性的，
歸并排序：它有一定數量的數據移動，所以我們可能過與插入排序組合，先獲得一定長度的序列，然后再合并，在效率上將有所提高。
2)當n較大，內存空間允許，且要求穩定性 =》歸并排序
3)當n較小，可采用直接插入或直接選擇排序。
直接插入排序：當元素分布有序，直接插入排序將大大減少比較次數和移動記錄的次數。
直接選擇排序 ：元素分布有序，如果不要求穩定性，選擇直接選擇排序
4)一般不使用或不直接使用傳統的冒泡排序。
5)基數排序
它是一種穩定的排序算法，但有一定的局限性：
1、關鍵字可分解。
2、記錄的關鍵字位數較少，如果密集更好
3、如果是數字時，好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。
