這節(jié)我們介紹直接插入排序和希爾排序算法,，

一、直接插入排序

直接插入排序(direct Insert Sort)的基本思想是：順序地將待排序的記錄按其關(guān)鍵碼的大小插入到已排序的記錄子序列的適當(dāng)位置,。 子序列的記錄個(gè)數(shù)從1開始逐漸增大,，當(dāng)子序列的記錄個(gè)數(shù)與順序表中的記錄個(gè)數(shù)相同時(shí)排序完畢。

設(shè)待排序的順序表 sqList 中有 n 個(gè)記錄,，初始時(shí)子序列中只有一個(gè)記錄sqList[0],。第一次排序時(shí)，準(zhǔn)備把記錄 sqList[1]插入到已排好序的子序列中,，這時(shí)只需要比較 sqList[0]和 sqList[1]的大小,，若 sqList[0]≤sqList[1]，說明序列已有序,，否則將 sqList[1]插入到 sqList[0]的前面,，這樣子序列的大小增大為 2,。第二次排序時(shí)，準(zhǔn)備把記錄 sqList[2]插入到已排好序的子序列中,，這需要先比較 sqList[2] 和 sqList[1]以確定是否需要把 sqList[2]插入到sqList[1]之前,。如果 sqList[2]插入到 sqList[1]之前，再比較 sqList[2]和sqList[0]以確定是否需要把 sqList[2]插入到 sqList[0]之前,。 這樣的過程一直進(jìn)行到 sqList[n-1]插入到子序列中為止,。這時(shí)，順序表 sqList 就是有序的,。如圖所示：

直接插入排序的算法如下所示,，算法中記錄的比較表示記錄關(guān)鍵碼的比較，順序表中只存放了記錄的關(guān)鍵碼：相應(yīng)源代碼如下：

//排序的插入排序的算法
public void InsertSort(SeqList<int> sqList) 
    { 
       //  從頭開始遍歷
          for (int i = 1; i < sqList.Last; ++i) 
          { 
               if (sqList[i] < sqList[i - 1]) 
               { 
                    //取數(shù)值較小的
                    int tmp = sqList[i]; 
                     //取首先的值
                     int j = 0; 
                    for (j = i - 1; j >= 0&&tmp<sqList[j]; --j) 
                    { 
                        sqList[j + 1] = sqList[j]; 
                    } 
                       //進(jìn)行賦值
                    sqList[j + 1] = tmp; 
                }
        } 
 }
//雙層循環(huán),，時(shí)間的復(fù)雜度是O(n2)

（1） 最好的情況是順序表中的記錄已全部排好序,。這時(shí)外層循環(huán)的次數(shù)為n-1，內(nèi)層循環(huán)的次數(shù)為 0,。這樣,，外層循環(huán)中每次記錄的比較次數(shù)為 1，所以直接插入排序算法在最好情況下的時(shí)間復(fù)雜度為 O(n),。
（2） 最壞情況是順序表中記錄是反序的,。這時(shí)內(nèi)層循環(huán)的循環(huán)系數(shù)每次均為 i。因此,，直接插入排序算法在最壞情況下的時(shí)間復(fù)雜度為O(n2),。 

（3） 如果順序表中的記錄的排列是隨機(jī)的，則記錄的期望比較次數(shù)為n2/4,。因此,，直接插入排序算法在一般情況下的時(shí)間復(fù)雜度為O(n2)。 可以證明,，順序表中的記錄越接近于有序,，直接插入排序算法的時(shí)間效率越高，其時(shí)間效率在O(n)到O(n2)之間,。
直接插入排序算法的空間復(fù)雜度為 O(1),。因此，直接插入排序算法是一種穩(wěn)定的排序算法,。什么是穩(wěn)定的排序算法,，就是前面與后面的數(shù)字相等的話，不用交換,。

二,、希爾排序

希爾排序又叫縮小增量法，屬于插入類排序,是將整個(gè)無序列分割成若干小的子序列分別進(jìn)行插入排序,。排序過程：先取一個(gè)正整數(shù)d1<n,，把所有序號(hào)相隔d1的數(shù)組元素放一組,，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1,，重復(fù)上述分組和排序操作,；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>

 /// <summary>
        /// Shell Sort
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="array"></param>
        public static void ShellSort<T>(T[] array) where T : IComparable
        {
                //長(zhǎng)度
            int length = array.Length;
            for (int h = length / 2; h > 0; h = h / 2)
            {
                //here is insert sort
                for (int i = h; i < length; i++)
                {
                    T temp = array[i];
//  進(jìn)行 漸變的  變量比較
                    if (temp.CompareTo(array[i -h]) < 0)
                    {
                        for (int j = 0; j < i; j += h)
                        {
                             //變量交換
                            if (temp.CompareTo(array[j]) < 0)
                            {
                                temp = array[j];
                                array[j] = array[i];
                                array[i] = temp;
                            }
                        }
                    }
                }
            }
        }
//算法的時(shí)間復(fù)雜度是O(n2)