這節我們介紹直接插入排序和希爾排序算法，

一、直接插入排序

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

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

直接插入排序的算法如下所示，算法中記錄的比較表示記錄關鍵碼的比較，順序表中只存放了記錄的關鍵碼：相應源代碼如下：

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

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

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

二、希爾排序

希爾排序又叫縮小增量法，屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序。排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。

?

相應的源代碼如下： /// <summary>/// Shell Sort/// </summary>/// <typeparam name="T"></typeparam>/// <param name="array"></param>public static void ShellSort<T>(T[] array) where T : IComparable{//長度int length = array.Length;for (int h = length / 2; h > 0; h = h / 2){//here is insert sortfor (int i = h; i < length; i++){T temp = array[i]; // 進行 漸變的 變量比較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;}}}}}}
//算法的時間復雜度是O(n2)

?

由于是三層循環，時間復雜度是O(n3)；這是一個不穩定的排序。 這節，我們介紹了直接插入排序和希爾排序。下節我們介紹，基數排序 ，簡單選擇排序 ，堆排序。

?

總結

以上是生活随笔為你收集整理的C#数据结构与算法揭秘17的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。