Linux C 算法——排序

排序(Sort)是將無序的記錄序列（或稱文件）調整成有序的序列。
為了方便討論，在此首先要對排序下一個確切的定義：
假設含有n個記錄的序列為
{ R1、R2、，。。。Rn }
其相應的關鍵字序列為
{K1、K2，。。。。Kn}
需確定1，2，。。。，n的一種排列 p1,p2,。。。pn，使其相應的關鍵字滿足如下的非遞減（或非遞增）關系
Kp1 <= Kp2 <=........<= Kpn
即使這個序列稱為一個按關鍵字有序的序列
{Rp1，Rp2,...., Rpn}
這樣的操作稱為排序。
排序分類：
1、穩定排序和非穩定排序
假設關鍵字 Ki = Kj (1 <= i <= n , 1<= j <= n , i != j )，且在排序前的序列中 Ri 領先於 Rj (即 i < j)。若在排序後的序列中，Ri 仍領先於 Rj ，則稱所用的排序方法是穩定的；反之，若可能使排序後的序列中Rj 領先於 Ri ，則稱所用的排序方法是不穩定的的。
2、內排序和外排序
內排序指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程；外排序是指待排序記錄的數量很大，以致內存依次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。
總之，在排序的過程中需進行下列兩種基本操作：1） 比較兩個關鍵字的大小 ；2）將記錄從一個位置移動到另一個位置；
下面討論內排序：

一、插入排序
1、[b]直接插入排序[/b]
直接排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表；
設待排文件f = (R1 R2 ........... Rn)相應的 key 集合為k = {k1 k2 ........kn }，其排序方法是：
現將文件中的（R1）看成只含一個記錄的有序子文件，然後從R2起，逐個將 R2 至 Rn按key插入到當前有序子文件中，最後得到一個有序的文件。插入的過程是一個key的比較過程，即每插入一個記錄時，將其key 與當前有序字表中的key進行比較，找到待插入記錄的位置後，將其插入即可。
[cpp] view
plain copy
#define maxsize 1024 //文件最大長度
typedef int key_t; //設key為整數
typedef struct //記錄類型
{
key_t key; //記錄關鍵字
..... //記錄其他域
}Retype;
typedef struct //文件或表的類型
{
Retype R[maxsize + 1]; //文件存儲空間
int len; //當前記錄數
}sqfile;
若說明sqfile F ； 則（F.R[1]，F.R[2]，。。。F.R[F.len] ）為待排文件，它是一種順序結構；文件長度 n = F.len ；F.R[0] 為工作單元，起到“監視哨”的作用；記錄的關鍵字ki 寫作 F.R[i].key 。
算法描述：
[cpp] view
plain copy
void Insort(sqfile F)
{
int i,j;
for(i = 2;i <= F;i++) //插入n - 1個記錄
{
F.R[0] = F.R[i]; //帶插入記錄先存於監視哨
j = i - 1;
while(F.R[0].key < F.R[j].key) //key 比較
{
F.R[j + 1] = F[j]; //記錄順序後移
j--;
}
F.R[j + 1] = F.R[0]; //原R[i]插入j + 1位置
}
}
排序的時間復雜度取耗時最高的量級，故直接插入排序的T(n) = O(n*n).
2、折半插入排序
排序算法的T(n) = O(n*n) ，是內排序時耗最高的時間復雜度。隨著文件記錄數n的增大，效率降低較快，下面的一些插入排序的方法，都是圍繞著改善算法的時間的復雜度而展開的。另外，直接插入排序是穩定排序。
為了減少插入排序過程中key的比較次數，可采用折半插入排序。
排序方法：
同直接插入排序，先將(R[1])看成一個子文件，然後依次插入R[2] .....R
。但在插入R[i] 時，子表（R[1] 。。。R[i-1]）已是有序的，查找R[i] 在子表中位置可按折半查找方法進行，從而降低key 的比較次數。
算法描述：
[cpp] view
plain copy
void Binsort(sqfile F) //對文件F折半插入排序的算法
{
int i,j,high,low,mid;
for(i = 2;i <= F.len,i++) //插入n-1個記錄
{
F.R[0] = F.R[i];//待插入記錄存入監視哨
low = 1;
high = i - 1;
while(low < high) //查找 R[i]的位置，即low = high 時；
{
mid = (low + high)/2;
if(F.R[0].key >= F.R[mid].key)
low = mid + 1; //調整下界
else
high =mid - 1;//調整上界
}
for(j = i - 1;j >= low;j--)
F.R[j + 1] = F.R[j]; //記錄瞬移
F.R[low] = F.R[0]; //原R[i]插入low位置
}
}
二、交換排序
1、起泡排序
設待排文件 f = (R1 R2 。。。Rn），相應key集合k = {k1 ,k2, ......kn}。
排序方法
從k1起，兩兩key比較，逆序時交換，即：
k1~k2，若 k1 > k2 ，則R1 與 R2 交換；
.....
k n-1 ~ kn，若kn-1 > kn ，則Rn-1 與 Rn 交換。
經過一趟比較之後，最大key的記錄沉底，類似水泡。接著對前n-1個記錄重復上述過程，直到排序完畢。
起泡排序的市價你復雜度 T(n) = O(n*n) 。
算法描述：
[cpp] view
plain copy
void Bubsort(sqfile F)
{
int i,flag; //flag 作為記錄交換的標志
Retype temp;
for(i = F.len;i > 2;i--) //最多n - 1次排序
{
flag = 0;
for(j = 1; j <= i - 1;j++) //一趟起泡排序
{
if(F.R[j].key > F.R[j + 1].key) //兩兩比較
{
temp = F.R[j]; //交換
F.R[j] = F.R[j + 1];
F.R[j + 1] = temp;
flag = 1;
}
flag = 1;
}
if(flag == 0) //無記錄交換時排序完畢
break;
}
}
2、快速排序
快速排序 的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。
一趟快速排序的算法是：
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-完成的時候，此時令循環結束）。
算法描述：
1）一趟快排算法
[cpp] view
plain copy
int Partition(sqfile *L,int low ,int high)
{
key_t pivotkey; //基准key
L->r[0] = L->r[low]; //存入基准記錄
pivotkey = L->r[low].key; //存入基准key
while(low < high)
{
while(low < high && L->r[high].key >= pivotkey) //逆序比較
high--;
if(low < high)
L->r[low] = L->r[high]; //比 pivotkey小的key左移
while(low < high && L->r[low].key <= pivotkey) //正序比較
low++;
if(low < high)
L->r[high] = L->r[low]; //比 pivotkey 大的右移
}
L->r[low] = L->r[0]; //基准記錄存入第i位置
return low; //返回基准位置
}
2）對文件L快速排序的算法（遞歸）
[cpp] view
plain copy
void QSort(sqfile *L,int low ,int high)
{
int pivotloc;
int i;
if(low < high)
{
pivotloc = Partition(L,low,high); //將L分成兩部分
QSort(L,low,pivotloc - 1); //對左部再排序
QSort(L,pivotloc + 1,high); //對右部再排序
}
}
下面是個測試程序：
[cpp] view
plain copy
#include <stdio.h>
#define maxsize 1024
typedef int key_t;
typedef struct
{
key_t key;
}Retype;
typedef struct
{
Retype r[maxsize + 1];
int len;
}sqlist;
int Partition(sqlist *L,int low ,int high)
{
key_t pivotkey;
L->r[0] = L->r[low];
pivotkey = L->r[low].key;
while(low < high)
{
while(low < high && L->r[high].key >= pivotkey)
high--;
if(low < high)
L->r[low] = L->r[high];
while(low < high && L->r[low].key <= pivotkey)
low++;
if(low < high)
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low;
}
void QSort(sqlist *L,int low ,int high)
{
int pivotloc;
int i;
if(low < high)
{
pivotloc = Partition(L,low,high);
QSort(L,low,pivotloc - 1);
QSort(L,pivotloc + 1,high);
}
}
int main()
{
int i;
sqlist L;
L.len = 8;
key_t a[8] = {50,36,66,76,36,12,25,95};
for(i = 1; i < 9; i++)
{
L.r[i].key = a[i - 1];
}
printf("Begin sorting!\n");
QSort(&L,1,8);
for(i = 1; i < 9; i++)
{
printf("%d ",L.r[i].key);
}
printf("\n");
return 0;
}
執行結果如下：
[cpp] view
plain copy
fs@ubuntu:~/qiang/sort$ ./quicksort
Begin sorting!
12 25 36 36 50 66 76 95