插入排序—直接插入排序

基本思想:
將一個(gè)記錄插入到已排序好的有序表中狭园，從而得到一個(gè)新读处，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列唱矛，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入罚舱，直至整個(gè)序列有序?yàn)橹埂?br> 要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用绎谦。

void InsertSort(int a[], int n)  
{  
    for(int i= 1; i<n; i++){  
        if(a[i] < a[i-1]){               //若第i個(gè)元素大于i-1元素管闷，直接插入。小于的話窃肠，移動(dòng)有序表后插入  
            int j= i-1;   
            int x = a[i];        //復(fù)制為哨兵包个，即存儲(chǔ)待排序元素  
            a[i] = a[i-1];           //先后移一個(gè)元素  
            while(x < a[j]){  //查找在有序表的插入位置  
                a[j+1] = a[j];  
                j--;         //元素后移  
            }  
            a[j+1] = x;      //插入到正確位置  
        }  
    }        
}  

穩(wěn)定性： 穩(wěn)定
效率：時(shí)間復(fù)雜度：O（n^2）

插入排序—希爾排序

基本思想:
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)冤留，再對全體記錄進(jìn)行依次直接插入排序碧囊。
操作方法：
1.選擇一個(gè)增量序列t1树灶，t2，…糯而，tk天通，其中ti>tj，tk=1歧蒋；
2.按增量序列個(gè)數(shù)k土砂，對序列進(jìn)行k 趟排序州既；
3.每趟排序谜洽，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列吴叶，分別對各子表進(jìn)行直接插入排序阐虚。僅增量因子為時(shí)，整個(gè)序列作為一個(gè)表來處理蚌卤，表長度即為整個(gè)序列的長度实束。
算法實(shí)現(xiàn)：
我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數(shù)的個(gè)數(shù)即：先將要排序的一組記錄按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組子序列，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行直接插入排序逊彭，然后再用一個(gè)較小的增量（d/2）對它進(jìn)行分組咸灿，在每組中再進(jìn)行直接插入排序。繼續(xù)不斷縮小增量直至為1侮叮，最后使用直接插入排序完成排序避矢。

void ShellInsertSort(int a[], int n, int dk)  
{  
    for(int i= dk; i<n; ++i){  
        if(a[i] < a[i-dk]){          //若第i個(gè)元素大于i-1元素，直接插入囊榜。小于的話审胸，移動(dòng)有序表后插入  
            int j = i-dk;     
            int x = a[i];           //復(fù)制為哨兵，即存儲(chǔ)待排序元素  
            a[i] = a[i-dk];         //首先后移一個(gè)元素  
            while(x < a[j]){     //查找在有序表的插入位置  
                a[j+dk] = a[j];  
                j -= dk;             //元素后移  
            }  
            a[j+dk] = x;            //插入到正確位置  
        }  
        print(a, n,i );  
    }  
      
}  
void ShellSort(int a[], int n){  
    int dk = n/2;  //先按增量d（n/2,n為要排序數(shù)的個(gè)數(shù)進(jìn)行希爾排序 
    while( dk >= 1  ){  
        ShellInsertSort(a, n, dk);  
        dk = dk/2;  
    }  
} 

穩(wěn)定性： 不穩(wěn)定
效率：關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取卸勺，時(shí)間復(fù)雜度：O（nlogn）~O(n^2)