我們已經詳解了插入排序和選擇排序，不了解的可以翻看我上一篇博客。

1冒泡排序

void BubbleSort(int* a, int n)
{int exchange = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){exchange = 1;swap(&a[j], &a[j + 1]);}}if (exchange == 0){break;}}
}

每次循環都會找到最大的元素放到最后一個位置上，以此往復完成排序。
如果在某一次循環exchange變成0，說明數組已然有序，直接退出循環即可。
時間復雜度：O(N^2 )
空間復雜度：O(1)

2.快速排序

快速排序是Hoare于1962年提出的?種?叉樹結構的交換排序?法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩?序列，左?序列中所有元素均?于基準值，右?序列中所有元素均?于基準值，然后最左右?序列重復該過程，直到所有元素都排列在相應位置上為?。
快速排序實現主框架：

void QuickSort(int* a, int left, int right)
{if (left >= right) {return;}//_QuickSort?于按照基準值將區間[left,right)中的元素進?劃分 int meet = _QuickSort(a, left, right);QuickSort(a, left, meet - 1);QuickSort(a, meet + 1, right);
}

_QuickSort這個函數應該怎么設計呢？

2.1hoare版本找基準值

int _QuickSort(int* a, int left, int right)
{int keyi = left;left++;while (left <= right){//right:從右往左找比基準值小的while (left <= right && a[right] > a[keyi]){right--;}//left:從左往右找比基準值大的while (left <= right && a[left] < a[keyi]){left++;}if (left <= right){Swap(&a[left++], &a[right--]);}}Swap(&a[keyi], &a[right]);//與小于基準值的交換return right;
}

2.2lomuto前后指針

設計兩個指針，cur指針負責遍歷整個數組并找見比基準值小的并于prev指向的交換，每次兩個指針都++,如果cur遇見比基準值大的prev就不動，直到遇到小于基準值的就另++prev指向的數據與cur指向的交換

int _QuickSort(int* a, int left, int right)
{int prev = left, cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur){swap(&a[cur], &a[prev]);}++cur;}swap(&a[key], &a[prev]);return prev;
}

時間復雜度：O(nlogn)
空間復雜度：O(logn)

3.非遞歸版本快速排序

這里就用到了我們前面實現的棧了。
我們知道，在快速排序中，數組中元素的交換是發生在找基準值這個過程中的，所以我們可以在棧中不斷放入left與right.直到棧為空。

void QuickSortNorR(int* arr, int left, int right)
{ST st;STInit(&st);STPush(&st,right);STPush(&st,left);while (!STEmpty(&st)){//取棧頂兩次int begini = STTop(&st);STPop(&st);int endi = STTop(&st);STPop(&st);//找基準值int keyi = _QuickSort(arr, begini, endi);if (keyi+1 < endi)//右序列[keyi+1,endi]{STPush(&st，endi);STPush(&st，keyi+1);}if (keyi -1> begini)//左序列[begini,keyi-1]{STPush(&st，keyi-1);STPush(&st，begini);}}Destroy(&st);
}

我們可以看到，這個版本中的邏輯其實也跟遞歸類似，都是一條路走到黑，直到序列中的left與rihgt不符合找基準值的條件。

4.遞歸排序

這張圖可以很好解釋歸并排序的思想，我們想要將數組拆分成多個子數組，將這多個子數組都變成有序，合并

void _MergrSort(int* arr, int left, int right,int*tmp)
{//分解if (left >= right){return;}int mid = (left + right) / 2;_MergrSort(arr, left, mid,tmp);_MergeSort(arr, mid + 1, right,tmp);//當程序走到這里時，[left,mid],[mid+1,right]已經變成兩個有序數組//合并兩個有序數組int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}for (int i = left;i <= right;i++){arr[i] = tmp[i];}}
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1,tmp);free(tmp);
}

時間復雜度：O(nlogn)
空間復雜度：O(n)

5.排序算法復雜度及穩定性分析

穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，?在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。


完
如果發現錯誤，歡迎打在評論區。
主頁還有更多優質內容OvO