目錄

前言：

插入排序：

希爾排序：

---

前言：

? ? 排序在我們生活中無處不在，比如學生成就排名，商品價格排名等等，所以排序在數據結構的學習中尤為重要，今天就為大家介紹兩個經典的排序算法：插入排序和希爾排序。

插入排序：

思路圖：

思路：

從第二個元素開始和前面的元素依次比較，如果前面的元素比它大，則將該元素移到后一位，如果該元素比它小，則直接插入該元素后面。

代碼實現：

void InsertSort(int* a, int n)
{int i = 0;for (i = 0;i < n-1;i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

時間復雜度：

? ? ? ?最壞情況下為O(N*N)，此時待排序列為逆序，或者說接近逆序
??最好情況下為O(N)，此時待排序列為升序，或者說接近升序。
空間復雜度：O(1)

希爾排序：

? 其實希爾排序就是插入排序的進階版，可以說是希爾對插入排序進行了優化。

思路圖：

思路：

步驟一：預排序，使數組接近有序

步驟二：插入排序

先將每間隔gap個元素的數據分為一組，將每組分別進行插入排序，使其接近有序

gap逐漸減小，gap減為1時就是進行步驟二的插入排序。

代碼實現：

void ShellSort(int* a, int n)
{int gap = n;while(gap>1){gap = gap / 2;int i = 0;for (i = 0;i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

紙上得來終覺淺，絕知此事要躬行。快去實踐一下吧。