數(shù)據(jù)結(jié)構(gòu)排序算法可以分為幾大類：插入排序

1.插入排序（Insertion Sort）

插入排序又可以分為

• 直接插入排序
• 折半插入排序
• 希爾排序

1.直接插入排序(Straight Insertion Sort)
算法基本思想：從第二個(gè)記錄起，逐個(gè)將每個(gè)未排序記錄直接插入前面已排好序的子序列哥纫。
基于該算法思想的流程圖

image.png

這里以一個(gè)具有10個(gè)元素的整型數(shù)組為例戚丸，給出直接插入排序算法的C語(yǔ)言實(shí)現(xiàn)代碼霞丧，首個(gè)存儲(chǔ)結(jié)點(diǎn)不存儲(chǔ)記錄，作為哨兵使用(相當(dāng)于起交換作用的temp變量)湃鹊，比如以數(shù)組A[n]為例儒喊，n個(gè)待排序記錄用size為n+1的數(shù)組來(lái)存儲(chǔ)，A[0]不存儲(chǔ)記錄币呵，A[1]--A[n]存儲(chǔ)記錄元素

#include<stdio.h>
int main(){
    int i,j;
    int A[11]={0,34,5,3,65,24,46,1,7,83,17}; //n為10怀愧，需要設(shè)置size為n+1的數(shù)組來(lái)存儲(chǔ)，這里默認(rèn)設(shè)置初始時(shí)哨兵A[0]為0
    for(i=2;i<=10;i++){ //從第一個(gè)待插入記錄開(kāi)始遍歷余赢，進(jìn)行n-1次插入
        if(A[i]<A[i-1]){ //A[i]為每次待插入的記錄芯义，A[i-1]為已排序記錄的最末位元素，按升序排序時(shí)妻柒，若A[i]大于A[i+1],則說(shuō)明此時(shí)不需要插入扛拨，最大元素剛好是此時(shí)的待插入記錄
            A[0]=A[i]; //但滿足上面一行if條件時(shí)，說(shuō)明需要插入举塔，才將需要插入的記錄值復(fù)制給哨兵
            for(j=i-1;A[j]>A[0];--j){ //j從已排序記錄最末位開(kāi)始绑警，逐次往前，當(dāng)已排序記錄關(guān)鍵字大于哨兵A[0]時(shí)央渣，將其右移一位
                A[j+1]=A[j];  //關(guān)鍵字大于哨兵A[0]的記錄右移一位
            }
            A[j+1]=A[0]; //將哨兵也就是待插入記錄插入該插入的位置计盒，此時(shí)的A[j]是小于等于哨兵的且A[j+1]大于哨兵，所以需要插入在A[j+1]位置
        }
    }
    for(i=1;i<=10;i++){
        printf("%d ",A[i]);
    }
    return 0;
}

這里在移動(dòng)元素時(shí)對(duì) j 使用 --j 前置自減芽丹，結(jié)果和 j--其實(shí)相同北启，只不過(guò)在處理大量數(shù)據(jù)時(shí)，前置自增自減要比后置自增自減性能表現(xiàn)好一些，先對(duì)待插入記錄和已排序列表最后一個(gè)記錄比較關(guān)鍵字大小暖庄，然后滿足if條件后才復(fù)制值給哨兵，而不是進(jìn)入for循環(huán)后直接先復(fù)制值給哨兵
程序運(yùn)行結(jié)果如下圖

image.png

image.png

這里的移動(dòng)次數(shù)包含每個(gè)待排序元素A[i]復(fù)制給哨兵A[0]的移動(dòng)和哨兵A[0]插入到A[j+1]的移動(dòng)，所以
最差情況下暂殖，待排序序列為逆序价匠，總的比較的次數(shù)C為2+3+...+n，需要移動(dòng)的次數(shù)C為3+4+...+(n+1)呛每，時(shí)間復(fù)雜度為O(n^2);
該算法平均比較次數(shù)和移動(dòng)次數(shù)都約為 (n^2)/4 踩窖，所以算法的時(shí)間復(fù)雜度為O(n^2)
穩(wěn)定性：由于每次插入時(shí)總是在排序子序列中從后往前先比較再移動(dòng)，所以不會(huì)出現(xiàn)關(guān)鍵字相同的記錄相對(duì)位置發(fā)生變化晨横，直接插入排序算法是穩(wěn)定的排序算法洋腮。
適用性：直接插入排序既適用于順序存儲(chǔ)的線性表，也適用于鏈?zhǔn)酱鎯?chǔ)的線性表手形。 （大部分排序算法都僅使用于順序存儲(chǔ)的線性表）

2.二分插入排序 (Binary Insert Sort)
算法基本思想：每次插入先利用二分查找確定應(yīng)當(dāng)插入的位置啥供，然后再移動(dòng)該位置及之后所有元素。
這里以一個(gè)有10個(gè)記錄的一維整型數(shù)組為例库糠，C語(yǔ)言實(shí)現(xiàn)代碼如下：

#include<stdio.h>
int main(){
    int i,j,low,high,mid;
    int A[11]={0,12,5,35,24,3,7,65,1,47,54};
    for(i=2;i<=10;i++){
        A[0]=A[i]; //先將待插入的元素復(fù)制給哨兵
        low=1; //低位指針從下標(biāo)1開(kāi)始伙狐，也就是第一個(gè)記錄元素
        high=i-1; //高位指針從已排序序列最末位，也就是當(dāng)前待插入元素A[i]前一個(gè)記錄瞬欧，所以為i-1贷屎；
        while(low<=high){ //while循環(huán)開(kāi)始進(jìn)行二分查找過(guò)程，當(dāng)滿足low<=high時(shí)才進(jìn)行二分查找
            mid=(low+high)/2; //mid只有在二分查找過(guò)程中賦值
            if(A[0]<A[mid]){ //哨兵A[0]與A[mid]中值不斷比較大小艘虎，若小于A[mid],說(shuō)明A[mid]右邊所有元素都比哨兵大豫尽，此時(shí)更換high指針為mid-1；
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        for(j=i-1;j>=high+1;--j){ //此時(shí)已經(jīng)從二分查找的while循環(huán)里面推出來(lái)顷帖，說(shuō)明已經(jīng)找到應(yīng)該插入的位置美旧，下標(biāo)為high+1，所有high+1及其右邊元素都右移1位
            A[j+1]=A[j];
        }
        A[high+1]=A[0]; //哨兵插入贬墩，一趟插入排序完成榴嗅，i代表的for循環(huán)繼續(xù)下一趟
    }
    for(i=1;i<=10;i++){
        printf("%d ",A[i]);
    }
    return 0;
}

和直接插入排序不同的是，二分插入排序沒(méi)有對(duì)待插入記錄和已排序序列中任何記錄進(jìn)行比較陶舞，也就是沒(méi)有用到 if 語(yǔ)句嗽测，進(jìn)入for循環(huán)后 直接先將待插入記錄值復(fù)制給哨兵，然后開(kāi)始二分查找過(guò)程，二分查找過(guò)程首先初始化low high指針唠粥，先有了high low指針值疏魏，才能開(kāi)始二分查找插入位置過(guò)程，才能有mid指針值晤愧，有了mid指針值大莫，就可以對(duì)哨兵和mid對(duì)應(yīng)的值進(jìn)行比較，根據(jù)比較結(jié)果對(duì)high low指針進(jìn)行調(diào)整官份，反復(fù)以此便可以找到插入位置然后退出while循環(huán)只厘，此時(shí)的插入位置為high+1。找到了插入位置后然后干什么呢舅巷？當(dāng)然是移動(dòng)插入位置及其右邊所有元素了羔味，這時(shí)利用 j的 for 循環(huán)移動(dòng)，移動(dòng)完所有元素后钠右，與直接插入排序不同的是赋元，將哨兵A[0]插入high+1處，而不是j+1 位置處飒房，一趟插入完成们陆。
程序運(yùn)行結(jié)果如圖：

image.png

性能分析
二分插入排序也是穩(wěn)定的排序算法，與直接插入排序所不同的是情屹，二分插入排序的比較次數(shù)減少坪仇，n個(gè)元素大約需要比較O(nlog2n) 次。比較的次數(shù)與元素初始序列狀態(tài)無(wú)關(guān)垃你，僅取決于元素個(gè)數(shù)n椅文，元素移動(dòng)的次數(shù)與初始序列狀態(tài)有關(guān)，時(shí)間復(fù)雜度也為O(n^2)惜颇，對(duì)于數(shù)據(jù)量不是很大的序列皆刺，二分插入排序性能表現(xiàn)很好。

3.希爾排序（Hill Sort）
算法基本思想：通過(guò)設(shè)置gap 間隔值凌摄，來(lái)將待排序序列分成若干組子序列羡蛾，每個(gè)子序列中前后相鄰兩個(gè)元素之間有gap-1個(gè)元素，一般設(shè)置gap初始值為n/2锨亏， n為待排序列總記錄個(gè)數(shù)痴怨，對(duì)每個(gè)子序列進(jìn)行直接插入排序，然后所有子序列 直接插入排序 執(zhí)行完之后gap取半向下取整進(jìn)行下一趟器予，直到gap值變?yōu)?浪藻，此時(shí)對(duì)整個(gè)序列進(jìn)行不用再劃分子序列，而是直接插入排序

如下圖所示乾翔，一個(gè)n為15的整型數(shù)組爱葵，初始時(shí)gap=15/2=7，然后依次取半向下取整為3，1萌丈，當(dāng)gap為7時(shí)赞哗，分成了8個(gè)子序列，每個(gè)子序列直接排序后的8個(gè)子序列為 {55辆雾，99} {5, 77} {48, 69} {12, 33} {56肪笋，88} {2, 13} {22, 69} {99, 99}, 然后gap折半向下取整為3，按照間隔元素?cái)?shù)為2可以用3個(gè)子序列包含全部元素乾颁，然后對(duì)這3個(gè)子序列各自依次使用直接插入排序涂乌，得到如下圖的第二圈排列結(jié)果艺栈，這時(shí)候gap再次折半向下取整為1英岭，gap為1時(shí)對(duì)整個(gè)序列使用 直接插入排序 算法，便可得到最終的排序序列湿右。

image.png

這里以一個(gè)具有10個(gè)記錄的一維整型數(shù)組為例诅妹，size為11，A[0]最終不存儲(chǔ)記錄毅人，作為temp交換變量使用 吭狡，給出一個(gè)C語(yǔ)言實(shí)現(xiàn)：

#include<stdio.h>
int main(){
    int i,j,gap;
    int A[11]={0,17,5,48,32,26,1,7,89,61,52}; // A[0]默認(rèn)設(shè)置為0
    for(gap=5;gap>0;gap/=2){ //判斷條件也可以寫成gap>=1,
        for(i=gap+1;i<11;++i){ //類比地看，此處開(kāi)始直接插入排序的實(shí)現(xiàn)過(guò)程丈莺，直接插入排序即gap為1 i=2划煮，gap之所以要+1是因?yàn)橛涗洀腁[1]開(kāi)始，所以 gap+1  - 1= gap 中間有 gap-1個(gè)元素缔俄，++i 和 i++在這里最終的結(jié)果相同弛秋，只不過(guò) ++i性能表現(xiàn)更好一些
            if(A[i]<A[i-gap]){ // 待插入記錄小于已排序序列最末位記錄時(shí)才需要移動(dòng)插入元素
                A[0]=A[i]; // 滿足if條件進(jìn)入這里說(shuō)明需要插入, 那先把待插入記錄復(fù)制給‘哨兵’A[0]了
                for(j=i-gap;j>0&&A[j]>A[0];j-=gap){ //開(kāi)始插入， 需要滿足j>0是因?yàn)锳[0]最終不存儲(chǔ)記錄俐载，所以需要移動(dòng)的元素下標(biāo)至少為1蟹略，子序列中上一個(gè)元素的位置要減去gap而不是1;
                    A[j+gap]=A[j]; //移動(dòng)子序列元素
                }
                A[j+gap]=A[0]; //插入‘哨兵’
            }
        }
    }
    for(i=1;i<11;i++){
        printf("%d ",A[i]);
    }
    return 0;
}

++i 和 i++在這里最終的結(jié)果相同，只不過(guò) ++i性能表現(xiàn)更好一些
程序執(zhí)行結(jié)果如下圖：

image.png

2.交換排序(Swap Sort)

交換排序主要有兩類

• 冒泡排序（Bubble Sort）
• 快速排序（Quick Sort）

1.冒泡排序 (Bubble Sort)
算法基本思想：從首個(gè)記錄開(kāi)始，像是有一個(gè)有兩個(gè)托盤的天平在未排序序列下端状婶，這兩個(gè)托盤托住兩個(gè)緊緊相鄰的未排序列元素意敛，從一側(cè)(未排序側(cè))起始元素開(kāi)始往另一側(cè)一步一步前進(jìn)，每一步對(duì)比托盤上的兩個(gè)元素大小膛虫，按照升序或降序的要求空闲，若需要?jiǎng)t交換這兩個(gè)元素，直至天平走到 其中一側(cè)托盤與已排序序列相鄰走敌，這時(shí)與已排序序列相鄰的托盤上的元素加入到已排序序列中碴倾，開(kāi)始下一趟冒泡。
算法的原理動(dòng)畫如下圖展示

冒泡排序.gif

冒泡排序.gif

以n為10的一維整型數(shù)組為例，按照升序排序跌榔，C語(yǔ)言簡(jiǎn)單實(shí)現(xiàn)如下：

include<stdio.h>
int main(){
    int i,j,temp;
    int A[10]={14,5,3,78,64,59,41,87,1,33};
    for(i=0;i<9;i++){ //需要冒泡 n-1趟异雁，i從0開(kāi)始，所以 i< n-1
        for(j=0;j<9-i;j++) {// 天平右側(cè)的托盤指針j+1要小于 n-i, 所以 j< n-i-1, 這里n為10 僧须，所以j < 9-i
            if(A[j]>A[j+1]){ //天平左邊的元素大于右邊的元素纲刀，需要交換
                temp=A[j]; //用temp輔助變量交換 A[j]與A[j+1]
                A[j]=A[j+1];
                A[j+1]=temp;
            }
        }
    }
    for(i=0;i<10;i++){
        printf("%d ", A[i]);
    }
    return 0;
}

程序運(yùn)行結(jié)果如下圖：

image.png

2.快速排序 (QuickSort)
算法基本思想：用一個(gè)稱為基準(zhǔn)的 pivot，一般取待排序列首個(gè)記錄或者最末位記錄暂论，將所有小于pivot的記錄劃分到左側(cè)面褐，所有大于等于pivot的記錄劃分到右側(cè)，劃分成兩個(gè)獨(dú)立的子塊取胎，這個(gè)過(guò)程稱為1趟快排或1次劃分展哭，然后分別對(duì)這兩個(gè)子塊遞歸,直至每個(gè)子塊僅包含1個(gè)或0個(gè)記錄，此時(shí)排序結(jié)束闻蛀。
一個(gè)簡(jiǎn)單的實(shí)例過(guò)程如圖：

image.png

快速排序有遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)匪傍，這里主要講遞歸實(shí)現(xiàn)方法，非遞歸實(shí)現(xiàn)的方法需要用到棧
遞歸實(shí)現(xiàn)觉痛，主要有兩個(gè)關(guān)鍵函數(shù)役衡，功能如下

• partition(int array[], int low, int high)
  劃分函數(shù)，通過(guò)low high指針不斷搜索交換記錄實(shí)現(xiàn)劃分薪棒，并最終定位到當(dāng)前pivot最終位置插入并返回值（此時(shí)low == high手蝎，因?yàn)閘ow high指針相向而行，步長(zhǎng)為1）
• quickSort(int array[], int low, int high),
  調(diào)用partition()函數(shù)獲取每一趟劃分最終得到的基準(zhǔn)位置盗尸，然后利用基準(zhǔn)位置前后相鄰兩個(gè)位置的下標(biāo)和low 柑船，high指針搭配作為參數(shù)遞歸調(diào)用自身

這里以n = 10的一維整型數(shù)組為例，一個(gè)C語(yǔ)言的簡(jiǎn)單實(shí)現(xiàn)：

#include<stdio.h>
#include<stdlib.h>
int partition(int array[], int low, int high){
    int pivot = array[low]; //這里基準(zhǔn)取第一位
    while(low < high){ //當(dāng)low == high 時(shí)泼各，說(shuō)明已經(jīng)找到了pivot最終位置鞍时，不需要再進(jìn)行劃分了
        while(low < high && array[high] >= pivot){ //從high開(kāi)始，與基準(zhǔn)pivot比較扣蜻，若大于等于pivot逆巍，則不需要交換，此時(shí)將high指針左移持續(xù)搜索莽使，直至找到小于pivot的記錄
            --high; // 因?yàn)橛野氩糠钟涗浂即笥诘扔趐ivot锐极，滿足條件，所以high指針左移
        }
        array[low] = array[high]; //退出上面這個(gè)循環(huán)芳肌，執(zhí)行到這里灵再，說(shuō)明high找到了小于pivot的記錄肋层，需要將其交換到low位置處,執(zhí)行玩這一步后，high處的位置相當(dāng)于“空下來(lái)”了, 實(shí)際上有記錄翎迁，但其可被覆蓋栋猖，毫無(wú)影響
        while(low < high && array[low] < pivot){ //當(dāng)高位high找到小于pivot的記錄并交換后，程序順序執(zhí)行到這里汪榔，從low低位開(kāi)始右移查找蒲拉，直至找到大于等于pivot的記錄
            ++low; // 因?yàn)樽蟀氩糠钟涗浂夹∮趐ivot，滿足條件痴腌，所以low指針左移
        }
        array[high] = array [low]; //low找到了左半部分大于等于pivot的記錄雌团，需要交換到high的“空位”上，
    } //while循環(huán)退出來(lái)士聪，說(shuō)明一次劃分已經(jīng)完成锦援，找到了pivot最終位置，即low的位置戚嗅，此時(shí)low == high雨涛，
    array[low] = pivot;
    return low;
}

void quickSort(int array[], int low, int high){ //數(shù)組第一次調(diào)用時(shí)枢舶，low為0懦胞，high為n-1
    if(low < high){ //low小于high時(shí)才需要遞歸劃分
        int pivotpos = partition(array, low, high); //獲取上一趟劃分pivot基準(zhǔn)最終位置
        quickSort(array, low, pivotpos-1); //根據(jù)上一趟的pivot位置，劃分的左半部分凉泄，low始終是0躏尉，high變成pivotpos-1，因?yàn)樯弦惶藙澐謕ivot在中間將序列切割成兩部分后众，
        quickSort(array, pivotpos+1, high);//根據(jù)上一趟pivot的位置胀糜，劃分的右半部分，high始終是n-1蒂誉；因?yàn)閿?shù)組第一次調(diào)用時(shí)教藻，low為0，high為n-1右锨，而low變成pivotpos+1
    }

}
int main(){
    int i;
    int A[] = {24,7,63,51,5,1,23,46,38,14};
    int n = sizeof(A) / sizeof(A[0]); //計(jì)算數(shù)組長(zhǎng)度
    quickSort(A, 0, n-1);
    for(i=0; i<n; i++){
        printf("%d ", A[i]);
    }
    return 0;
}

程序運(yùn)行結(jié)果如下圖：

image.png

1.簡(jiǎn)單選擇排序

• 算法基本思想：從未排序元素中選取一個(gè)最小值 括堤，放到已排序序列的末端，反復(fù)以此绍移。
  這里以一個(gè)具有10個(gè)元素的整型數(shù)組為例悄窃，給出簡(jiǎn)單選擇排序算法的C語(yǔ)言實(shí)現(xiàn)代碼，

#include<stdio.h>
int main(){
    int i,j,min,temp;
    int A[10]={12,3,7,25,68,54,36,98,1,2};
    for(i=0;i<9;i++){ //i小于數(shù)組長(zhǎng)度減1蹂窖，因?yàn)樾枰舗-1趟轧抗，選n-1個(gè)最小值，那么剩下那一個(gè)必然是最大值瞬测，位于排序序列最后
        min=i; //用整型數(shù)據(jù)min作為指針來(lái)記錄最小值元素的下標(biāo)横媚，初始時(shí)指向未排序序列首個(gè)元素
        for(j=i+1;j<10;j++){ //j是從未排序序列元素第二個(gè)元素開(kāi)始循環(huán)遍歷的纠炮，所以j從i+1開(kāi)始，因?yàn)閷?duì)i而言灯蝴，每一趟都會(huì)確定一個(gè)最小值放在已排序序列最后抗碰，所以j最多可以等于數(shù)組長(zhǎng)度減1
            if(A[j]<A[min]){ 
                min=j; //min指針指向此時(shí)最小的元素
            } //至此，j循環(huán)用min指針確定了未排序序列中最小值的下標(biāo)
        }
        if(min!=i){ //若未排序序列最小值元素不在未排序序列首位绽乔，就用temp輔助變量交換未排序序列最小值元素和未排序序列首個(gè)元素的位置
            temp=A[i];
            A[i]=A[min];
            A[min]=temp;
        }
    }
    for(i=0;i<10;i++){ //依次打印排序后所有元素的值
        printf("%d ",A[i]);
    }
    return 0;
}

程序運(yùn)行結(jié)果如下圖

SelectSort.png

性能分析