前言：前面我們已經學過了許許多多的排序方法，如冒泡排序，選擇排序，堆排序等等，那么我們就來將排序的方法總結一下。

我們的排序方法包括以下幾種，而快速排序和歸并排序我們后面進行詳細的講解。

直接插入排序：

void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n - 1; ++i){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;}
}

直接插入排序顧名思義把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
我們用一個變量來保存我們插入數據的原數組中的后一個數據，我們排的是降序，那么我們的后一個數據比前一個數據大的話，我們的后一個數據tmp就被前一個覆蓋，直到end<0或者我們的后一個數據比前一個小我們就跳出循環，我們保存的數據就等于我們跳出循環的這個數。

希爾排序：

void ShellSort(int* a, int n)
{int gap = n;// gap > 1時是預排序，目的讓他接近有序// gap == 1是直接插入排序，目的是讓他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;for (int 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是我們沒組兩個樹之間的間隔， 如果我們的gap是3時，我們就分成了三組，當gap等于0時，我們的紅色這組就進行插入排序，當gap為1時，我們藍色這組就進行插入排序，當gap為2時，我們綠色這組就進行插入排序，這樣我們將完成了第一趟排序。我們要完成整個排序的話，我們就得在嵌套一層循環，我們的gap大于1時就進行預排序，我們的gap為1時就是最后一趟排序，我們的gap無論是幾，只要最后gap的值為1我們就完成了排序。

選擇排序：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

我們這里用兩個變量來保存小數和大數的下標，我們的后面循環里的數如果比下標為0的數小的話，小數據mini的下標就是我們比第一個數據小的數據i的坐標，我們排序排的是升序，我們的第一個數就是應該是下標為mini的數據，所以我們將就下標為mini的數據與第一個數據交換，們的后面循環里的數如果比下標為0的數大的話就是存放大數據，下標為maxi，我們就用最后一個數據和下標為maxi的數據交換。如果我們最后循環退出的時候我們的maxi還等于begin，那么我們的下標為begin的數據就是最小的。

堆排序：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假設左孩子小，如果解設錯了，更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

我們要排升序，所以我們需要建立一個大堆，大堆的特點是子節點大于根節點，我們通過不斷將根節點和最后一個節點交換，進行向下調整，我們的數據大的節點就會沉在底下，而小的節點就會浮在上面，最后我們通過遍歷就能夠輸出升序的數據。

冒泡排序：

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}

冒泡排序我們很早之前就已經了解過了，我這里就不多贅述了，如果有疑問的話就看我之前的文章
https://blog.csdn.net/Lehjy/article/details/132266676，相信以你的聰明才智一定可以完美的解決。

最后感謝大家一如既往的支持！謝謝大家！