????????歡迎來到繁星的CSDN，本期的內容主要包括冒泡排序(BubbleSort），直接插入排序(InsertSort)，以及插入排序進階版希爾排序（ShellSort）。

????????廢話不多說，直接上正題！

一、冒泡排序

? ? ? ? 冒泡排序是我們的老朋友了，我們最初模擬實現qsort的時候就是用它來模擬的（盡管qsort的底層原理實際是quicksort，即快排）。

? ? ? ? 上代碼！

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){// 單趟int flag = 0;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0){break;}}
}

? ? ? ? 代碼相當簡單，其思想就是通過兩兩之間的比較，每一趟都將最大的數據放在數組的最后。

? ? ? ? 缺點是，冒泡排序的速度相當慢，原因不僅僅在于比較的次數恒定（n*(n+1)/2次)，更在于如果數據量龐大，各個數據移動的速度也相當慢。

? ? ? ? 實際意義聊勝于無，但卻很好地幫我們入門各大排序算法，這是它仍然活躍的意義。

? ? ?二、直接插入排序

? ? ? ?我們一般會叫它插入排序，在此加入“直接”二字，是為了區分它和希爾排序。

? ? ? ? 插入排序的思路也是較為簡單的。

? ? ? ? 面對一個有n個元素的數組，如果前n-1個元素都有序，那么第n個元素通過和前面所有元素比較，就能得到該元素在數組中的位置。有一點數學歸納法的思想在里面。

? ? ? ? 上代碼！

void InsertSort(int* a, int n)
{//  [0, n-1]for (int i = 0; i < n - 1; i++){// [0, n-2]是最后一組// [0,end]有序 end+1位置的值插入[0,end]，保持有序int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

? ? ? ? 由于一個元素一定有序，所以第一個元素不用排序。而從第二個元素開始，通過比較，不斷插入到前面的數組中，使前n項都有序，如此往復，便可使得整個數組有序。

? ? ? ? 相比于冒泡排序，插入排序少了大量重復的交換數值的工作，而是一步到位，得到數據的最終位置（盡管時常需要將所有數據后移，但代碼中只是賦值，而非交換，效率比冒泡高的多）。

? ? ? ? 兩者運行時間差別：

????????

? ? ? ? （此處數據為10000個）

? ? ? ? 盡管如此，我們在實際工作中也很少使用直接插入排序，即使時間比冒泡排序少的多，其時間復雜度仍為O(n^2)。但不得不指出，它仍有應用，后續在快排的時候將會提到。

三、希爾排序

????????

????????希爾排序是插入排序的優化版本，優化到可以和快速排序一較高下。

????????希爾排序主要做兩件事：1、預排序。2、插入排序。

? ? ? ? 由插入排序的代碼可知，當數組越趨近于有序，比較和賦值的次數也越來越少。所以預排序的目的就是使得整個數組接近有序。

? ? ? ? 上代碼！

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保證最后一個gap一定是1// gap > 1時是預排序// gap == 1時是插入排序gap = gap / 3 + 1;for (size_t i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

? ? ? ? 要點解釋：

1、gap代表的含義是，下標相減為gap的元素為一組，進行插入排序。此舉的意義是使得O（n^2)的復雜度造成的影響盡可能小，因為a*(n/a)^2小于n^2，a為任意整數。

2、而當gap等于1時再進行排序，就是插入排序了。

3、gap的大小實際上由寫代碼的人自己決定，沒有一定gap越大，或者gap越小的效果最好，但可以確定的是，經過預排序的插排會比直接插排要更快。

4、上述代碼中的gap是一個效果較好的gap，可以參照并直接使用。

????????本篇內容到此結束，謝謝大家的觀看！

????????覺得寫的還不錯的可以點點關注，收藏和贊，一鍵三連。

? ? ? ? 我們下期再見~

? ? ? ? 往期欄目：

????????一文帶你入門二叉樹！-CSDN博客

????????棧和隊列的介紹與實現-CSDN博客

????????設計掃雷游戲_掃雷游戲設計-CSDN博客

????????

????????