代碼準(zhǔn)備：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

//1.排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
//用于要排序數(shù)組個(gè)數(shù)最大值耙饰，可根據(jù)需要修改
#define MAXSIZE 10000
typedef struct
{
    //用于存儲(chǔ)要排序數(shù)組谣沸，r[0]用作哨兵或臨時(shí)變量
    int r[MAXSIZE+1];
    //用于記錄順序表的長(zhǎng)度
    int length;
}SqList;


//2.排序常用交換函數(shù)實(shí)現(xiàn)
//交換L中數(shù)組r的下標(biāo)為i和j的值
void swap(SqList *L,int i,int j)
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//3.數(shù)組打印
void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);
    printf("%d",L.r[i]);
    printf("\n");
}

歸并排序

歸并排序(Merging Sort) 就是利用歸并的思想實(shí)現(xiàn)排序方法. 它的原理是假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列. 每個(gè)子序列的?長(zhǎng)度為1,然后兩合并.得到[n/2]個(gè)長(zhǎng)度為2或1的有序子序列, 再兩兩歸并. ......如此重復(fù),直到得到一個(gè)長(zhǎng)度為n 的有序列為此. 這種排序方法稱為2路路歸并排序
代碼實(shí)現(xiàn)

//③ 將有序的SR[i..mid]和SR[mid+1..n]歸并為有序的TR[i..n]
void Merge(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    //1.將SR中記錄由小到大地并入TR
    for(j=m+1,k=i;i<=m && j<=n;k++)
    {
        if (SR[i]<SR[j])
            TR[k]=SR[i++];
        else
            TR[k]=SR[j++];
    }
    
    //2.將剩余的SR[i..mid]復(fù)制到TR
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)
            TR[k+l]=SR[i+l];
    }
    
    //3.將剩余的SR[j..mid]復(fù)制到TR
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            TR[k+l]=SR[j+l];
    }
}


//② 將SR[s...t] 歸并排序?yàn)?TR1[s...t];
void MSort(int SR[],int TR1[],int low, int hight){
    int mid;
    int TR2[MAXSIZE+1];
    
    if(low == hight)
        TR1[low] = SR[low];
    else{
        //1.將SR[low...hight] 平分成 SR[low...mid] 和 SR[mid+1,hight];
        mid = (low + hight)/2;
        //2. 遞歸將SR[low,mid]歸并為有序的TR2[low,mid];
        MSort(SR, TR2, low, mid);
        //3. 遞歸將SR[mid+1,hight]歸并為有序的TR2[mid+1,hight];
        MSort(SR, TR2, mid+1, hight);
        //4. 將TR2[low,mid] 與 TR2[mid+1,hight], 歸并到TR1[low,hight]中
        Merge(TR2, TR1, low, mid, hight);
    }
}

//① 對(duì)順序表L進(jìn)行歸并排序
void MergeSort(SqList *L){
   
    MSort(L->r,L->r,1,L->length);
}

//12.歸并排序(非遞歸)-->對(duì)順序表L進(jìn)行非遞歸排序
//對(duì)SR數(shù)組中相鄰長(zhǎng)度為s的子序列進(jìn)行兩兩歸并到TR[]數(shù)組中;
void MergePass(int SR[],int TR[],int s,int length){
  
    int i = 1;
    int j;
    
    //①合并數(shù)組
    //s=1 循環(huán)結(jié)束位置:8 (9-2*1+1=8)
    //s=2 循環(huán)結(jié)束位置:6 (9-2*2+1=6)
    //s=4 循環(huán)結(jié)束位置:2 (9-2*4+1=2)
    //s=8 循環(huán)結(jié)束位置:-6(9-2*8+1=-6) s = 8時(shí),不會(huì)進(jìn)入到循環(huán);
    while (i<= length-2*s+1) {
        //兩兩歸并(合并相鄰的2段數(shù)據(jù))
        Merge(SR, TR, i, i+s-1, i+2*s-1);
        i = i+2*s;
        
        /*
         s = 1,i = 1,Merge(SR,TR,1,1,2);
         s = 1,i = 3,Merge(SR,TR,3,3,4);
         s = 1,i = 5,Merge(SR,TR,5,5,6);
         s = 1,i = 7,Merge(SR,TR,7,7,8);
         s = 1,i = 9,退出循環(huán);
         */
        
        /*
         s = 2,i = 1,Merge(SR,TR,1,2,4);
         s = 2,i = 5,Merge(SR,TR,5,6,8);
         s = 2,i = 9,退出循環(huán);
         */
        
        /*
         s = 4,i = 1,Merge(SR,TR,1,4,8);
         s = 4,i = 9,退出循環(huán);
         */
    }
    
    //②如果i<length-s+1,表示有2個(gè)長(zhǎng)度不等的子序列. 其中一個(gè)長(zhǎng)度為length,另一個(gè)小于length
    // 1 < (9-8+1)(2)
    //s = 8時(shí), 1 < (9-8+1)
    if(i < length-s+1){
        //Merge(SR,TR,1,8,9)
        Merge(SR, TR, i, i+s-1, length);
    }else{
        //③只剩下一個(gè)子序列;
        for (j = i; j <=length; j++) {
            TR[j] = SR[j];
        }
    }
}

void MergeSort2(SqList *L){
    int *TR = (int *)malloc(sizeof(int) * L->length);
    int k = 1;
    //k的拆分變換是 1,2,4,8;
    while (k < L->length) {
        //將SR數(shù)組按照s=2的長(zhǎng)度進(jìn)行拆分合并,結(jié)果存儲(chǔ)到TR數(shù)組中;
        //注意:此時(shí)經(jīng)過第一輪的歸并排序的結(jié)果是存儲(chǔ)到TR數(shù)組了;
        MergePass(L->r, TR, k, L->length);
        k = 2*k;
        //將剛剛歸并排序后的TR數(shù)組,按照s = 2k的長(zhǎng)度進(jìn)行拆分合并. 結(jié)果存儲(chǔ)到L->r數(shù)組中;
        //注意:因?yàn)樯弦惠喌呐判虻慕Y(jié)果是存儲(chǔ)到TR數(shù)組,所以這次排序的數(shù)據(jù)應(yīng)該是再次對(duì)TR數(shù)組排序;
        MergePass(TR, L->r, k, L->length);
        k = 2*k;
        
    }
}

快速排序

快速排序(Quick Sort)的基本思想: 通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)?立的兩部分; 其中一部分記錄的關(guān)鍵字均為另一部分記錄的關(guān)鍵字小,則可分別對(duì)兩部分記 錄繼續(xù)進(jìn)行排序,以達(dá)到整個(gè)排序有序的目的.
代碼實(shí)現(xiàn)：

//③交換順序表L中子表的記錄夺脾，使樞軸記錄到位角溃，并返回其所在位置
//此時(shí)在它之前(后)的記錄均不大(小)于它
int Partition(SqList *L,int low,int high){
    int pivotkey;
    //pivokey 保存子表中第1個(gè)記錄作為樞軸記錄;
    pivotkey = L->r[low];
    //① 從表的兩端交替地向中間掃描;
    while (low < high) {
        
        //② 比較,從高位開始,找到比pivokey更小的值的下標(biāo)位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        //③ 將比樞軸值小的記錄交換到低端;
        swap(L, low, high);
        //④ 比較,從低位開始,找到比pivokey更大的值的下標(biāo)位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        //⑤ 將比樞軸值大的記錄交換到高端;
        swap(L, low, high);
        
    }
    
    //返回樞軸pivokey 所在位置;
    return low;
}

//② 對(duì)順序表L的子序列L->r[low,high]做快速排序;
void QSort(SqList *L,int low,int high){
    int pivot;
    
    if(low < high){
        //將L->r[low,high]一分為二,算出中樞軸值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //對(duì)低子表遞歸排序;
        QSort(L, low, pivot-1);
        //對(duì)高子表遞歸排序
        QSort(L, pivot+1, high);
    }
    
}

//① 調(diào)用快速排序(為了保證一致的調(diào)用風(fēng)格)
void QucikSort(SqList *L){
    QSort(L, 1, L->length);
}

//14 快速排序-優(yōu)化
int Partition2(SqList *L,int low,int high){
   
    int pivotkey;
    
    /**1.優(yōu)化選擇樞軸**/
    //① 計(jì)算數(shù)組中間的元素的下標(biāo)值;
    int m = low + (high - low)/2;
    //② 將數(shù)組中的L->r[low] 是整個(gè)序列中左中右3個(gè)關(guān)鍵字的中間值;
    //交換左端與右端的數(shù)據(jù),保證左端較小;[9,1,5,8,3,7,4,6,2]
    if(L->r[low]>L->r[high])
        swap(L, low, high);
    //交換中間與右端的數(shù)據(jù),保證中間較小; [2,1,5,8,3,7,4,6,9];
    if(L->r[m]>L->r[high])
        swap(L, high, m);
    //交換中間與左端,保證左端較小;[2,1,5,8,3,7,4,6,9]
    if(L->r[m]>L->r[low])
        swap(L, m, low);
    //交換后的序列:3,1,5,8,2,7,4,6,9
    //此時(shí)low = 3; 那么此時(shí)一定比選擇 9,2更合適;
    
    
    /**2.優(yōu)化不必要的交換**/
    //pivokey 保存子表中第1個(gè)記錄作為樞軸記錄;
    pivotkey = L->r[low];
    //將樞軸關(guān)鍵字備份到L->r[0];
    L->r[0] = pivotkey;
    
    //① 從表的兩端交替地向中間掃描;
    while (low < high) {
        //② 比較,從高位開始,找到比pivokey更小的值的下標(biāo)位置;
        while (low < high &&  L->r[high] >= pivotkey)
            high--;
        
        //③ 將比樞軸值小的記錄交換到低端;
        //swap(L, low, high);
        //③ 采用替換的方式將比樞軸值小的記錄替換到低端
        L->r[low] = L->r[high];
        
        //④ 比較,從低位開始,找到比pivokey更大的值的下標(biāo)位置;
        while (low < high && L->r[low] <= pivotkey)
            low++;
        
        //⑤ 將比樞軸值大的記錄交換到高端;
        //swap(L, low, high);
        //⑤ 采樣替換的方式將比樞軸值大的記錄替換到高端
        L->r[high] = L->r[low];
    }
    //將樞軸數(shù)值替換會(huì)L->r[low]
    L->r[low] = L->r[0];
    
    //返回樞軸pivokey 所在位置;
    return low;
}

//② 對(duì)順序表L的子序列L->r[low,high]做快速排序;
#define MAX_LENGTH_INSERT_SORT 7 //數(shù)組長(zhǎng)度的閥值
void QSort2(SqList *L,int low,int high){
    int pivot;
    //if(low < high){
    //當(dāng)high-low 大于常數(shù)閥值是用快速排序;
    if((high-low)>MAX_LENGTH_INSERT_SORT){
        //將L->r[low,high]一分為二,算出中樞軸值 pivot;
        pivot = Partition(L, low, high);
        printf("pivot = %d L->r[%d] = %d\n",pivot,pivot,L->r[pivot]);
        //對(duì)低子表遞歸排序;
        QSort(L, low, pivot-1);
        //對(duì)高子表遞歸排序
        QSort(L, pivot+1, high);
    }else{
        //當(dāng)high-low小于常數(shù)閥值是用直接插入排序
        InsertSort(L);
    }
}

//① 快速排序優(yōu)化
void QuickSort2(SqList *L)
{
    QSort2(L,1,L->length);
}