本文转载自：http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm
排序(Sorting)
排序(sorting)，將一組資料一使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料，優點為容易閱讀、統計分析、與快速搜尋所要之資料。
「資料結構」課程中，排序法分分類方式有三類：
第一類：內部與外部排序
內部排序(Internal sort)又稱「陣列排序」。
【定義】排序之工作，主要在主記憶體(RAM)完成。
【適用時機】資料量較少者。
外部排序(External sort)又稱「檔案排序」。
【定義】排序之工作，主要是在輔助記憶體(Disk, File)完成。
【適用時機】資料量較大者。
第二類：穩定與不穩定排序法
穩定排序法(stable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序。
【例如】
排序前：3,5,19,1,3*,10
排序後：1,3,3*,5,10,19 (因為兩個3, 3*的相對位置在排序前與後皆相同。)
不穩定排序法(unstable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前不相同時，稱不穩定排序。
【例如】
排序前：3,5,19,1,3*,10
排序後：1,3*,3,5,10,19 (因為兩個3, 3*的相對位置在排序前與後不相同。)
第三類：簡單與高等排序法
簡單排序法
【定義】排序演算法簡單，但執行時間較長。
【平均時間複雜度】
高等排序法
【定義】排序演算法複雜，執行時間較短。
【平均時間複雜度】
常見之排序演算法
常見之排序演算法：氣泡排序、選擇排序、插入排序、快速排序、堆積(heap)排序、薛爾(shell)排序、合併排序、基數排序
|
排序方法 |
最壞時間 |
平均時間 |
穩定 |
額外空間 |
備註說明 |
|
氣泡排序 Bubble |
O(n2) |
O(n2) |
穩定 |
O(1) |
n小比較好。 |
|
選擇排序 Selection |
O(n2) |
O(n2) |
不穩定 |
O(1) |
n小較好，部份排序好更好。 |
|
插入排序 Insertion |
O(n2) |
O(n2) |
穩定 |
O(1) |
大部份排序好比較好。 |
|
快速排序 Quick |
O(n2) |
O(nlog2n) |
不穩定 |
O(n)~ O(log n) |
在資料已排序好時會產生最差狀況。 |
|
堆積排序 Heap |
O(nlog2n) |
O(nlog2n) |
不穩定 |
O(1) |
|
|
薛爾排序 shell |
O(ns) 1<s<2 |
O(n(log2n)2) |
穩定 |
O(1) |
n小比較好。 |
|
合併排序 Merge |
O(nlog2n) |
O(nlog2n) |
穩定 |
O(n) |
常用於外部排序。 |
|
基數排序 Radix |
O(nlogbB) |
O(n)~ O(nlogbk) |
穩定 |
O(nb) |
k:箱子數 b:基數 |
氣泡排序(Bubble sorting)
資料結構中最簡單之排序法。所謂氣泡排序法就是相臨資料互相比較，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將如氣泡般，依次由下往上浮起。
【分析】
1. 比較之回合數=資料數(n)-1。
2. 每一回合至少有一資料可以排列至正確之次序。
3. 時間複製度，最差與平均時間O(n2)
4. 需要一個額外(元素)空間。
5. 為一穩定排序。
6. 資料量小時，使用效果佳。
【原理】
1. 每一回合逐一比較相臨資料，依排序之順序交換位置。
2. 每回合至少會有一次交換位置，至沒交換位置則停止。
【演算法】
BubSort(int A[], int n) //氣泡排序法之副程式
{
int i, j , k,t=1, Temp,sp;
for (i=n-1; i>0; i--)
{
sp=1;
for (j =0; j <=i; j++)
if (A[j] > A[j+1])
{ //兩數交換位置
Temp = A[j];
A[j] = A[j+1];
A[j+1] = Temp;
sp=0;
}
if (sp==1) break;
}
}
選擇排序(Selection sorting)
類似於氣泡排序法。主要差異在於，第n回合比較時，以一額外資料空間儲存目前第n大(小)，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將由最大(最小)逐回合比較至最小(最大)。
【分析】
1. 比較之回合數=資料數(n)-1。
2. 時間複製度：最差與平均時間O(n2)
3. 需要一個額外(元素)空間。
4. 為一穩定排序。
5. 資料量小時，使用效果佳(優於氣泡)。
【原理】
1. 未排序前之第一筆資料可視為已排序好之資料
2. 每一回合逐一比較相臨資料，依排序之順序交換位置。
【演算法】
SelSort(int A[], int n) //選擇排序法之副程式
{
int i, j, Temp, NP = 0;
for (i = 1; i <= n - 1; i++)
{
NP = i;
for (j = i + 1; j <= n; j++)
if (A[j] > A[NP]) NP = j;
{//相鄰兩個的資料交換位置
Temp = A[i];
A[i] = A[NP];
A[NP] = Temp;
}
}
}
插入排序(Insertion sorting)
每次往後拿一筆記錄，依大小插入已排序好的記錄。也就是說，差入一個記錄在一堆已排好序之記錄中。任何未排序前之第一筆資料可視為已排序好之資料。
【分析】
1. 時間複製度，最差與平均時間O(n2)
2. 只需要一個額外(元素)空間。
3. 為一穩定排序。
4. 此方法適用於大部份資料已排序或已排序之資料庫新增資料後進行排序。
【原理】
1. 將待排序之資料逐一與已排序後之資料比較，再將資料放入適當位置。
2. 由最大(最小)逐回合比較至最小(最大)。
【演算法】
InSort(int A[], int n) //插入排序法之副程式
{
int i, j, Temp;
for (i = 1; i <= n; i++)
{
Temp=A[i];
j=i-1;
while (Temp<A[j])
{
A[j+1]=A[j];
j--;
if(j==-1) break;
}
A[j+1]=Temp;
}
}
快速排序(Quick sorting)
快速排序之觀念，找資料之中間值，將小於中間值放右邊，大於中間值放左邊，再以相同方法分左右兩邊序列，直到排序完成。
【分析】
1. 時間複製度，最差O(n2)與平均時間O(nlog2n)。
2. 需要額外堆疊空間。
3. 為不穩定排序。
4. 快速排序是平均時間最快之內部排序法。
【原理】
1. 取第一個記錄為鍵值K0，當中間值。
2. 由左而右找第一個Ki，使得Ki≧K0。由右而左找第一個Kj，使得Kj≦K0。也就是說，從左邊找比K0大，從右邊找比K0小。
3. 若i<j則Ki與Kj對調位置繼續步驟2；否則K0與Kj對調位置，並以j為基準，分為兩個未排序之序列。以遞迴呼叫方式對左右兩邊進行排序，直道完成排序。
4. 由最大(最小)逐回合比較至最小(最大)。
【演算法】
QuickSort(int A[], int left, int right)
{
int i, j, s , Temp;
if(left < right) {
s = A[(left+right)/2];
i = left - 1;
j = right + 1;
while(1) {
while(A[++i] < s) ; // 向右找
while(A[--j] > s) ; // 向左找
if(i >= j) break;
Temp = A[i];
A[i] = A[j];
A[j] = Temp;
}
QuickSort(A, left, i-1); // 對左邊進行遞迴
QuickSort(A, j+1, right); // 對右邊進行遞迴
}
}
堆積排序(Heap sorting)
【分析】
1. 時間複製度，最差與平均時間O(nlog2n)。
2. 只需一額外記錄空間。
3. 為不穩定排序。
【原理】
1. 。
【演算法】
Heapsort(int A[]) {
int i, m, p, s,t=1;
m = MAX;
while(m > 1) {
SWAP(A[1], A[m]);
m--;
p = 1;
s = 2 * p;
while(s <= m) {
if(s < m && A[s+1] < A[s]) s++;
if(A[p] <= A[s]) break;
SWAP(A[p], A[s]);
p = s;
s = 2 * p;
}
}
}
薛爾排序(Shell sorting)
【分析】
1. 時間複製度，最差O(ns)與平均時間O(n(log2n)2)。
2. 為穩定排序。
【演算法】
Shellsort(int A[])
{
int i, j, k, Gap, t;
Gap = MAX / 2;
while(Gap > 0)
{
for(k = 0; k < Gap; k++)
{
for(i = k+Gap; i < MAX; i+=Gap)
{
for(j = i - Gap; j >= k; j-=Gap)
{
if(A[j] > A[j+Gap])
{
SWAP(A[j], A[j+Gap]);
}
else break;
}
}
}
printf("\nGap = %d：", Gap);
for(i = 0; i < MAX; i++)
printf("%d ", A[i]);
Gap /= 2;
}
}
合併排序(Merge sorting)
【演算法】
Mergesort(int A[], int M, int B[],int N, int C[])
{
int i = 0, j = 0, k = 0;
while(i < M && j < N)
{
if(A[i] <= B[j]) C[k++] = A[i++];
else C[k++] = B[j++];
}
while(i < M) C[k++] = A[i++];
while(j < N) C[k++] = B[j++];
}
基數排序(Radix sorting)
【演算法】
Radix(int data[],int n)
{ int t=1;
while(n <= 10)
{
for(i = 0; i < 10; i++)
{
lsd = ((data[i] / n) % 10);
temp[lsd][order[lsd]] = data[i];
order[lsd]++;
}
if (t==1) printf("\n「個位數」為主排序：");
else printf("\n「十位數」為主排序：");
for(i = 0; i < 10; i++)
{
if(order[i] != 0)
for(j = 0; j < order[i]; j++)
{
data[k] = temp[i][j];
printf("%d ", data[k]);
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
t+=1;
}
}