1 冒泡排序(優(yōu)化)
2 選擇排序
3 直接插入排序
4 希爾排序
5 堆排序
6 歸并排序(優(yōu)化)
7 快速排序(優(yōu)化)

#define MAXSIZE 10000  /* 用于要排序數(shù)組個(gè)數(shù)最大值，可根據(jù)需要修改 */
typedef struct
{
    int r[MAXSIZE+1];   /* 用于存儲(chǔ)要排序數(shù)組，r[0]用作哨兵或臨時(shí)變量 */
    int length;         /* 用于記錄順序表的長(zhǎng)度 */
}SqList;

1 冒泡排序

兩兩比較相鄰的數(shù)據(jù),如果反序則交換,直到?jīng)]有反序的記錄
//改進(jìn)冒泡排序
//在性能上有一些提升,避免因已經(jīng)有序的情況下的無(wú)意義循環(huán)判斷

void maoPao(SqList *L){
    Status flag = TRUE;
    //若flag為true則退出循環(huán)
    for (int i = 1; i < L->length && flag; i++)
    {
        flag = FALSE;
        for (int j = L->length - 1; j >= 1; j--)
        {
            if (L->r[j] > L->r[j+1])
            {
                int temp = L->r[i];
                L->r[i] = L->r[j];
                L->r[j] = temp;
                flag = TRUE;
            }
        }
    }
}

2 選擇排序

//通過(guò)n-i次關(guān)鍵字間的比較,從n-i+1個(gè)數(shù)據(jù)中選出關(guān)鍵字最小的數(shù)據(jù),并和第i(1<=i<=n)個(gè)數(shù)據(jù)交換

void xuanZe(SqList *L){
    int min;
    for (int i = 1; i < L->length; i++)
    {
        //將當(dāng)前下標(biāo)定義為最小值下標(biāo)
        min = i;
        //循環(huán)當(dāng)前下標(biāo)之后的所有數(shù)據(jù)
        for (int j = i+1; j <= L->length; j++)
        {
            //j=2 L[1]>L[2] 9>1
            //min=2
            //j=3 L[2]>L[3] 1>5
            //min不變,還是2
            if (L->r[min] > L->r[j])
            {
                min = j;
            }
        }
        //全比較過(guò)后,交換值
        if (i != min)
        {
            int temp=L->r[i];
            L->r[i]=L->r[min];
            L->r[min]=temp;
        }
    }
}

3 直接插入排序

//將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序表中,得到一個(gè)新的有序表

//r[6] = {0,5,3,4,6,2}
void chaRu(SqList *L){
    int i,j;
    for (i = 2; i < L->length; i++)
    {
        //i=2,053462,3<5
        //i=3,035462,4<5接著執(zhí)行
        if (L->r[i] < L->r[i-1])
        {
            //設(shè)置哨兵
            //r0 = 3
            L->r[0] = L->r[i];
            //j=1 5>3成立,走循環(huán)體
            //j=0 3>3不成立,出循環(huán),此時(shí)j為0
            for (j=i-1; L->r[j] > L->r[0]; j--)
            {
                //r2=5
                L->r[j+1] = L->r[j];
            }
            //r1=3
            L->r[j+1] = L->r[0];
        }
    }
}

4 希爾排序

//實(shí)際上是優(yōu)化的直接插入排序,采取跳躍分割的策略,將相距某個(gè)"增量"的記錄組成一個(gè)子序列,保證子序列內(nèi)分別進(jìn)行直接插入排序結(jié)果基本有序(大的基本在后面)
//時(shí)間復(fù)雜度為O(n3/2),比O(n2)要好點(diǎn)

void xiEr(SqList *L){
    int i,j;
    int zeng = L->length;
    do{
        //增量序列
        zeng = zeng/3 + 1;
        //分段排序,與直接插入排序相同
        for (i = zeng+1; i <= L->length; i++)
        {
            //判斷是否交換
            if (L->r[i] < L->r[i-zeng])
            {
                L->r[0] = L->r[i];
                for (j = i-zeng; j>0 && L->r[j] > L->r[0]; j-=zeng)
                {
                    L->r[j+zeng] = L->r[j];
                }
                L->r[j+zeng] = L->r[0];
            }
        }
    //增量為1時(shí),停止循環(huán)
    } while (zeng > 1);
}

5 堆排序

//對(duì)簡(jiǎn)單選擇排序進(jìn)行的一種改造,時(shí)間復(fù)雜度為O(nlogn),比冒泡,選擇,插入的O(n2)好很多
//堆是一種近似完全二叉樹(shù):利用完全二叉樹(shù)的深度是(log2n)+1的特性
//每個(gè)結(jié)點(diǎn)的值都大于或等于左右孩子結(jié)點(diǎn)的值,為大頂堆
//每個(gè)結(jié)點(diǎn)的值都小于或等于左右孩子結(jié)點(diǎn)的值,為小頂堆
//將待排序的序列構(gòu)造成一個(gè)大頂堆,整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn),將它移走,然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)大頂堆,反復(fù)執(zhí)行
//就是將堆數(shù)組的根結(jié)點(diǎn)與末尾元素交換,末尾元素就變成最大值了

//將數(shù)組調(diào)整為大頂堆
void daDingDui(SqList *L,int s,int m);
void dui(SqList *L){
    int i;
    //把有子節(jié)點(diǎn)的結(jié)點(diǎn)調(diào)整成大頂堆
    for (i = L->length/2 ; i>0 ; i--)
    {
        daDingDui(L, i, L->length);
    }
    for (i = L->length; i>1 ; i--)
    {
        //將堆頂數(shù)據(jù)和當(dāng)前未經(jīng)排序子序列的最后一個(gè)數(shù)據(jù)交換
        //把最大值換到尾巴處
        int temp=L->r[i];
        L->r[i]=L->r[1];
        L->r[1]=temp;
        //排除最后一個(gè)最大數(shù)據(jù),再重新調(diào)整成大頂堆
        daDingDui(L, 1, i-1);
    }
}

void daDingDui(SqList *L,int s,int m){
    int temp,j;
    temp= L->r[s];
    //沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選
    //根據(jù)完全二叉樹(shù)的按層序遞增排列特點(diǎn)
    //從j=2s開(kāi)始,j=m結(jié)束
    for (j=2*s ; j<=m ; j*=2)
    {
        //j為左孩子下標(biāo),j+1為右孩子下標(biāo),找出最大的
        if (j<m && L->r[j] < L->r[j+1])
        {
            ++j;
        }
        //比較根結(jié)點(diǎn)大小
        if (temp >= L->r[j])
        {
            break;
        }
        //把最大值給根結(jié)點(diǎn)
        L->r[s] = L->r[j];
        s = j;
    }
    //把剛開(kāi)始保存的較小值給子結(jié)點(diǎn)
    L->r[s] = temp;
}

6 歸并排序

//歸并--將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表
//2路歸并排序:n個(gè)數(shù)據(jù),兩兩歸并,直到得到一個(gè)長(zhǎng)度為n的有序序列
//總的時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n+logn)
//比較占用內(nèi)存,但是穩(wěn)定,效率高

//歸并函數(shù)
void realGuiBing(int SR[],int TR1[],int s,int t);
//排序函數(shù)
void Merge(int SR[],int TR[],int s,int m,int t);

//調(diào)用歸并函數(shù)
void guiBing(SqList *L){
    realGuiBing(L->r,L->r,1,L->length);
}

//遞歸函數(shù),將 SR[s...t] 歸并排序?yàn)?TR1[s...t]
void realGuiBing(int SR[],int TR1[],int s,int t){
    int m;
    int TR2[MAXSIZE +1];
    //相等就不用排序了
    if (s == t)
    {
        TR1[s] = SR[s];
    }
    else
    {
        //將SR[s...t]平分為SR[s...m]和SR[m+1...t]
        m = (s+t)/2;
        //遞歸將SR[s...m]歸并為有序的TR2[s...m]
        realGuiBing(SR,TR2,s,m);
        //遞歸將SR[m+1...t]歸并為有序的TR2[m+1...t]
        realGuiBing(SR,TR2,m+1,t);
        //將TR2[s...m]和TR2[m+1...t]歸并到TR1[s...t]
        Merge(TR2,TR1,s,m,t);
    }
}

//關(guān)鍵函數(shù),排序并合并
//將有序的SR[i...m] 和 SR[m+1...n]歸并為有序的TR[i...n]
void Merge(int SR[],int TR[],int s,int m,int t){
    int j,k,l;
    //將SR中數(shù)據(jù)由小到大歸并入TR
    for (j = m+1, k = s; s <= m && j <= t; k++)
    {
        if (SR[s] < SR[j])
        {
            TR[k] = SR[s++];
        }
        else
        {
            TR[k] = SR[j++];
        }
    }
    //將剩余的SR[s...m]復(fù)制到TR
    if (s <= m)
    {
        for (l = 0; l <= m-s; l++)
        {
            TR[k+1] = SR[s+1];
        }
    }
    //將剩余的SR[j...t]復(fù)制到TR
    if (j <= t)
    {
        for (l = 0; l < t-j; l++)
        {
            TR[k+1] = SR[j+1];
        }
    }
}

//優(yōu)化歸并排序,非遞歸實(shí)現(xiàn)

//非遞歸增加的函數(shù)
void MergeAdd(int SR[], int TR[],int s,int n);
//歸并排序
void guiBing2(SqList *L){
    //申請(qǐng)內(nèi)存空間
    int *TR = (int *)malloc(L->length *sizeof(int));
    int k = 1;
    while (k < L->length)
    {
        MergeAdd(L->r, TR, k, L->length);
        //子序列長(zhǎng)度加倍
        k = 2*k;
        MergeAdd(TR, L->r, k, L->length);
        //加倍
        k = 2*k;
    }
}

void MergeAdd(int SR[], int TR[],int s,int n){
    int i = 1;
    int j;
    while (i <= n - 2 * s + 1)
    {
        //兩兩歸并
        Merge(SR, TR, i, i + s - 1, i + 2 *s -1);
        i = i +2 *s;
    }
    //歸并最后兩個(gè)序列
    if (i < n-s+1)
    {
        Merge(SR, TR, i, i+s-1, n);
    }
    //剩下的單數(shù)直接并入
    else
    {
        for (j = i; j <= n; j++)
        {
            TR[j] = SR[j];
        }
    }
}

//希爾排序?yàn)橹苯硬迦肱判虻纳?jí),屬于插入排序類
//堆排序?yàn)楹?jiǎn)單選擇排序的升級(jí),屬于選擇排序類
//快速排序?yàn)槊芭菖判虻纳?jí),屬于交換排序類

7 快速排序

//通過(guò)一趟排序?qū)⒋艛?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分key均比另一部分key小,分別對(duì)這兩部分記錄繼續(xù)排序,最終完成排序
//時(shí)間復(fù)雜度平均為O(nlogn)

//快速排序
void realKuaiSu(SqList *L,int low,int high);
//找到樞軸值
int fenKai(SqList *L ,int low,int high);
//調(diào)用快速排序
void kuaiSu(SqList *L){
    realKuaiSu(L,1,L->length);
}
//快速排序
void realKuaiSu(SqList *L,int low,int high){
    int pivot;
    if (low < high)
    {
        //將L->r[low...high]一分為二,算出樞軸值pivot
        pivot = fenKai(L,low,high);
        //對(duì)低子表遞歸排序
        realKuaiSu(L,low,pivot-1);
        //對(duì)高子表遞歸排序
        realKuaiSu(L,pivot+1,high);
    }
}

//找到樞軸值,交換順序表L中子表的數(shù)據(jù)
//將選取的樞軸值不斷變換,將比它小的換到它的左邊,比它大的換到它的右邊,它也在交換中不斷更改自己的位置,直到完全滿足這個(gè)要求為止
int fenKai(SqList *L ,int low,int high){
    int pivotkey;
    //用子表的第一個(gè)數(shù)據(jù)做樞軸數(shù)據(jù)
    pivotkey = L -> r[low];
    //從表的兩端交替向中間掃描
    while (low < high)
    {
        //比樞軸數(shù)據(jù)小的數(shù)據(jù)交換到低端
        while (low < high && L->r[high] >= pivotkey)
        {
            high--;
            int temp=L->r[low];
            L->r[low]=L->r[high];
            L->r[high]=temp;
        }
        //將比樞軸大的數(shù)據(jù)交換到高端
        while (low < high && L->r[low] <= pivotkey)
        {
            low++;
            int temp=L->r[low];
            L->r[low]=L->r[high];
            L->r[high]=temp;
        }
    }
    return low;
}

//快速排序優(yōu)化

//1.選取樞軸pivotkey的優(yōu)化
//三數(shù)取中法:取左,中,右三個(gè)數(shù)據(jù)先排序,將中間數(shù)作為樞軸
//九數(shù)取中法
int getPivotkey(SqList *L,int high,int low){
    int pivotkey;
    //計(jì)算數(shù)組中間元素的下標(biāo)
    int m = low + (high - low)/2;
    //交換左右端數(shù)據(jù),保證左端較小
    if (L->r[low] > L->r[high])
    {
        int temp=L->r[low];
        L->r[low]=L->r[high];
        L->r[high]=temp;
    }
    //交換中間與右端數(shù)據(jù),保證中間較小
    if (L->r[m] > L->r[high])
    {
        int temp=L->r[m];
        L->r[m]=L->r[high];
        L->r[high]=temp;
    }
    //交換中間與左端數(shù)據(jù),保證左端較小
    if (L->r[m] > L->r[low])
    {
        int temp=L->r[m];
        L->r[m]=L->r[low];
        L->r[low]=temp;
    }
    //L.r[row]為三個(gè)關(guān)鍵字中間值
    pivotkey = L->r[low];
    return pivotkey;
}

//2.優(yōu)化不必要的交換
int youHuaKuaiSu(SqList *L,int low,int high){
    //取到樞軸
    int pivotkey = getPivotkey(L, high, low);
    //將樞軸備份
    L->r[0] = pivotkey;
    //從表的兩端交替向中間掃描
    while (low < high)
    {
        //比樞軸數(shù)據(jù)小的數(shù)據(jù)交換到低端
        while (low < high && L->r[high] >= pivotkey)
        {
            high--;
            //采用替換不是交換
            L->r[low] = L->r[high];
        }
        //將比樞軸大的數(shù)據(jù)交換到高端
        while (low < high && L->r[low] <= pivotkey)
        {
            low++;
            //采用替換不是交換
            L->r[high] = L->r[low];
        }
    }
    //將樞軸數(shù)值替換回L.r[low]
    L->r[low] = L->r[0];
    //返回樞軸所在位置
    return low;
}

//因?yàn)檫f歸的使用,非常大的數(shù)組用快速排序,直接插入排序是簡(jiǎn)單排序中性能最好的

經(jīng)過(guò)優(yōu)化的快速排序是性能最好的排序算法
從最好情況看,選擇冒泡和直接插入排序
從最壞情況看,選擇堆排序與歸并排序
從穩(wěn)定性來(lái)看,選擇歸并排序
如果執(zhí)行算法的軟件所處的環(huán)境非常在乎內(nèi)存使用量的多少,選擇堆排序等