插入排序

每次選擇一個(gè)元素K插入到之前已排好序的部分A[1…i]中，由后向前移動(dòng)元素直到找到一個(gè)合適的位置。
插入排序是穩(wěn)定的（相等的時(shí)候表示找到合適位置了，就不需要再移動(dòng)元素了）。

void InsertSort(RecType R[], int n){
    int i, j;
    RecType temp;
    for(i = 1; i<n; ++i){
        temp = R[i];
        j = i - 1;//從后往前找到一個(gè)合適的位置
        while(j >= 0 && temp.key < R[j].key){
            R[j + 1] = R[j];
            j--;
        }
        R[j + 1] = temp;//將元素放置到該合適位置
    }
}

冒泡排序

通過(guò)交換元素，使關(guān)鍵字最大的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。

排序過(guò)程中只交換相鄰兩個(gè)元素的位置。因此，當(dāng)兩個(gè)數(shù)相等時(shí)，是沒(méi)必要交換兩個(gè)數(shù)的位置的。所以，它們的相對(duì)位置并沒(méi)有改變，冒泡排序算法是穩(wěn)定的

void BubbleSort(RecType R[], int n){
    int i, j;
    RecType temp;
    for(i=0; i<n-1; i++){//每個(gè)元素
        bool flag = false;
        for(j=n-1;j > i; j--){//對(duì)每個(gè)元素進(jìn)行冒泡
             if(R[j].key < R[j - 1].key){
                 temp = R[j];
                 R[j] = R[j - 1];
                 R[j - 1] = temp;
                 flag = true;
            }
            if(!flag){//如果沒(méi)有交換，說(shuō)明已經(jīng)有序了
                return;
            }
        }
   }
} 

選擇排序

搜索無(wú)序數(shù)組，找到當(dāng)前最小的元素，并與無(wú)序數(shù)組首元素交換，縮小整個(gè)無(wú)序數(shù)組，并重復(fù)操作。直到整個(gè)數(shù)組有序。
由于每次都是選取未排序序列A中的最小元素x與A中的第一個(gè)元素交換，因此跨距離了，很可能破壞了元素間的相對(duì)位置，因此選擇排序是不穩(wěn)定的！

void SelectSort(RecType R[], int n){
    int i, j, k;
    RecType temp;
    for(i = 0; i < n - 1; ++i){
        k = i;
       //便利無(wú)序數(shù)組，找到最小的元素
        for(j = i + 1; j < n; j++){
            if(R[j].key < R[k].key){
                k = j;
            }
        }
        if(k != i){
           swap(R[i], R[k]);
        }
}

希爾排序

思想：希爾排序也是一種插入排序方法,實(shí)際上是一種分組插入方法。先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,把表的全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中,在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?br> 希爾排序時(shí)間復(fù)雜度平均為O(nlogn)