數據結構：從插入排序到希爾排序

插入排序(C語言版)

說明：

　　算法思路：

　　每次從無序表中取出第一個元素，將其插入到有序表中的適當位置，使有序表的長度不斷加長，完成排序過程。
　　n個待排序的元素由一個有序表和一個無序表組成,開始時有序表中只包含一個元素。

  　 流程演示：

　　　　
　　　　藍色表示由有序表，黑色表示無序表！

　　分析

　　　　元素基本有序時，直接插入排序的時間復雜度接近於O(n)
  　　　 元素數目n較少時，直接插入排序的效率較高

數據結構定義：

　　首先我們要構建一個順序表來存放待排序的元素！ 　　

　　這是我排序的基礎，我的所有的排序算法都會依賴於這個簡單的順序表！

typedef  int  KeyType;              // 定義關鍵字類型為整型
typedef  int  InfoType;

typedef struct  {
    KeyType    key;                  // 關鍵字項
    InfoType  otherinfo;          // 其他數據項
}RedType;                               // 記錄類型

typedef struct {
    RedType r[MAXSIZE+1];    // r[0]閒置或用作哨兵
    int length;                            // 順序表長度
}SqList;

　　編寫了兩個方法可以對順序表進行初始化和遍歷

void initSqList(SqList & S)
{
    int t,count=0;
    while(scanf("%d",&t)!=0)
    {
        count++;
        S.r[count].key=t;
    }
    S.length=count;
}

void traverseSqList(SqList S)
{
    for(int i=1;i<=S.length;i++)
        printf("%d",S.r[i].key);
}

優化的直接插入排序

我們在這裡采用了優化，我們進行的是元素的移動和覆蓋，而不僅僅是簡單的交換。

void sortByDirectlyInsert(SqList &L)
{
    for(int i = 2; i <= L.length; i++)      //第一個元素默認有序，所以直接從2開始
        if (L.r[i].key < L.r[i-1].key) {    //這裡進行了優化，如果i >i-1，說明從1～i這一段都是有序的，我們不需要進行後續操作
            L.r[0] = L.r[i];    
            L.r[i] = L.r[i-1];
            int j;
            for(j = i - 2;L.r[0].key < L.r[j].key; j--)
                L.r[j+1] = L.r[j];
            L.r[j+1] = L.r[0];
        }//if
}

思路舉例：
　　[ ]5 9 6 3 8 //待排序元素
　　[ ]5 9 //到這裡是有序的
　　[ ]5 9 6 //到這裡發現6小於9
　　　　[6 ]5 9 空 //將6移到監視哨，把它的位置空出來
　　　　[6 ]5 空 9 //讓9來到原來6的位置，把9的位置空出來，看看6能不能填在那裡
　　　　[6 ]5 6 9 //6可以填在那裡，讓空的位置等於監視哨
　　[]5 6 9 3
　　　　[3 ]5 6 9 空
　　　　[3 ]5 6 空 9
　　　　[3 ]5 空 6 9
　　　　[3 ]空 5 6 9
　　　　[3 ]3 5 6 9
　　[]3 5 6 9 8
　　　　[8 ]3 5 6 9 空
　　　　[8 ]3 5 6 空 9
　　　　[8 ]3 5 6 8 9
　　[]3 5 6 8 9

進一步優化版的插入排序

我們這樣想，既然左半部分是是有序的，我們在有序的數組中找到插入位置，最好的方法非二分查找莫屬。

void sortByBinaryDirectlyInsert(SqList &L)
{
    for(int i=2;i <= L.length; i++)
    {   L.r[0] = L.r[i];                /* 保存待插入元素 */
        int low = 1,high = i-1;    /* 設置初始區間 */
        while(low <= high)       /* 確定插入位置 */
        {   int mid = (low+high)/2;
            if (L.r[0].key > L.r[mid].key)
                low = mid+1;      /* 插入位置在高半區中 */
            else
                high = mid-1;   /* 插入位置在低半區中 */
        }/* while */
        for(int j = i - 1; j >= high +1;  j--) /* high+1為插入位置 */
            L.r[j+1] = L.r[j];          /* 後移元素，留出插入空位 */
        L.r[high+1] = L.r[0];      /* 將元素插入 */
    }/* for */
}

希爾排序

算法思想：

　　先將整個待排序元素序列分割成若干個小序列，在小序列內插入排序；
　　逐漸擴大小序列的長度（序列個數減少），使得整個序列基本有序；
　　最後再對全體元素進行一次直接插入排序。

代碼實現：

void ShellInsert(SqList &L,int dk)  {//對順序表L作一趟希爾排序
    for(int i =dk+1; i <= L.length; i++)
        if (L.r[i].key < L.r[i-dk].key) {
            L.r[0] = L.r[i];
            int j;
            for(j = i - dk;  j>0 &&L.r[0].key < L.r[j].key;  j -= dk)
                L.r[j+dk] = L.r[j];
            L.r[j+dk] = L.r[0];
        }//if
} //ShellInsert
void ShellSort(SqList &L,int dlta[],int t)  {
    //按增量序列dlta[0..t-1]進行希爾排序
    for(int k = 0; k < t; k++)
        ShellInsert(L,dlta[k]);     //一趟增量為dlta[k]的希爾排序
} //ShellSort

  說明：

　　1.希爾排序的實質是插入排序！希爾排序的分析是一個復雜的問題，增量序列的設置是關鍵，尚沒有正式的依據說明何種設置最為合理！

　　2.空間復雜度為O(1),是一種不穩定的排序算法！