目錄
- 前言
- 非線性時間比較類
- 插入排序
- (1) 直接插入排序
- (2) 希爾排序
- 選擇排序
- (3) 選擇排序優化版
- (4) 堆排序
- 交換排序
- (5) 冒泡排序
- (6) 快速排序
- hoare版本
- 挖坑版
- 前后指針版
- 非遞歸版
- 歸并排序
- (7) 歸并排序
- 遞歸版
- 非遞歸版
- 線性時間比較類
- (8) 計數排序
- 基數排序與桶排序
- 總結
前言
在計算機科學中，排序算法是一種重要的算法類別，用于將一組元素按照特定的順序進行排列。排序算法的應用非常廣泛，從日常生活中的字典排序到大規模數據處理中的并行排序，都離不開排序算法的支持。
本博客將介紹十種常見的排序算法，包括冒泡排序、插入排序、選擇排序、快速排序、歸并排序、堆排序、希爾排序、計數排序、(桶排序和基數排序,稍作了解)。每種算法都會詳細講解其原理、時間復雜度、空間復雜度等關鍵知識點，以及對比不同算法的優劣勢。
通過學習這十種常見的排序算法，讀者將能夠深入理解算法設計和分析的思想，提升自己的編程能力和解決問題的能力。無論是面試、競賽還是實際項目開發，掌握好排序算法都是非常有幫助的。
希望本博客能對讀者有所幫助，讓大家能夠更好地應用排序算法解決實際問題。如果對于排序算法還有疑問或者建議，歡迎留言交流。讓我們一起進入排序算法的世界，開拓自己的算法視野！
博客主頁: 酷酷學!!! 感謝關注! 您的支持是我的極大動力
非線性時間比較類
插入排序
更多詳情點擊: 博客鏈接
(1) 直接插入排序
時間復雜度：O(N^2)
最壞：逆序
最好：順序有序，O(N)
// 插入排序
void InsertSort(int* a, int n)
{//默認升序for (int i = 0; i < n - 1; i++)//最后一次將最后一個元素記錄下來,就不要循環到n{//int end = 0;//先寫內層循環,定義下標end,假設第一個元素有序int end = i;//進行改寫,假設前i個位置有序int tmp = a[end + 1];//記錄后一個位置的元素while (end >= 0)//從end下標位置開始依次比較{if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;//此時a[end+1]位置就是需要插入的位置,跳出循環再插入是為了防止end=0時,//循環無法進入,此時無法進行賦值}
}
(2) 希爾排序
希爾排序是一種排序算法，屬于插入排序的一種改進版本。它通過將數組分成若干個子序列，對每個子序列進行插入排序，然后逐步減少子序列的長度，最終完成排序。希爾排序的核心思想是將數組按照一定間隔分組，然后對每組進行插入排序。這樣可以減少比較和交換的次數，從而提高排序的效率。
時間復雜度: O(N ^ 1.3)
// 希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//每次縮小三倍效率是比較高的,+1是為了防止gap==0循環進不來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;}}
}
選擇排序
更多詳情點擊: 博客鏈接
(3) 選擇排序優化版
這里直接給出優化版代碼, 采用雙指針法, 同時選出到最大與最小的元素位置.
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}// 選擇排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){//雙指針法int min = begin, max = begin;//假設a[begin]為最大和最小值for (int i = begin + 1; i <= end; i++)//選出最大最小元素,保存下標{if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[min], &a[begin]);if (max == begin)//如果begin位置還是max,最大值就被交換到了min位置,故需要判斷{max = min;}Swap(&a[max], &a[end]);begin++;end--;}
}
(4) 堆排序
堆排序（Heap Sort）是一種效率較高的排序算法，它的基本思想是將待排序的序列構建成一個大頂堆，然后將堆頂元素與末尾元素交換，再重新調整堆，直到整個序列有序
//向上調整算法,假設建小堆
//比如插入一個新元素,還需要保證是堆的結構就需要進行調整
void AdjustUP(int* a, int child)
{//首先需要找到它的父親結點int parent = (child - 1) / 2;//不管是左孩子還是右孩子都能算出父節點while (child > 0)//這里用child進行條件判斷,用parent<=0會進入死循環,然后巧合結束,不規范{if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;//讓父節點等于孩子結點,繼續找父節點parent = (child - 1) / 2;}else{break;}}
}
// 堆排序
//如果要刪除堆頂元素,不可以直接刪除,這樣會破壞堆的結構,應該先把堆頂數據與最后一個數據交換
//然后刪除最后一個數據,此時再將堆頂元素進行向下調整,直到滿足堆的性質,調整要保證左右子樹也都是堆
void AdjustDwon(int* a, int n, int root)
{//排升序,建大堆//先假設左孩子大int child = root * 2 + 1;while (child < n)//到最后一個孩子就結束{//右孩子存在且比左孩子大if (child + 1 < n && a[child + 1] > a[child]){child = child + 1;}if (a[child] > a[root]){Swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}
}
//這里用向下調整建堆,效率更高
void HeapSort(int* a, int n)
{//從最后一個非葉子結點開始建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}//建堆完畢,將第一個元素與最后一個元素交換,再次調整int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDwon(a, end, 0);//此時調整最后一個元素之前的數組end--;}
}
交換排序
更多詳情點擊: 博客鏈接
(5) 冒泡排序
冒泡排序是一種簡單的交換排序算法，它通過不斷地比較相鄰的元素，如果順序不對就交換它們的位置，直到整個列表或數組排好序。
快速排序是一種高效的交換排序算法，它通過選擇一個基準元素，將小于基準元素的元素放在它的左邊，大于基準元素的元素放在它的右邊，然后再對左右兩部分進行遞歸調用快速排序，直到整個列表或數組排好序。
交換排序的時間復雜度通常是O(n^2)，但在最好情況下，快速排序的時間復雜度可以達到O(nlogn)
//冒泡排序
void BubbleSort(int* a, int n)
{//先寫內層循環//先找出最大的for (int i = 0; i < n - 1 ; i++){int flag = 1;//兩兩比較,先找最大的,然后找次大的for (int j = 0; j < n - 1 - i; j++)//i代表找到了幾個最大的{if (a[j] > a[j + 1]){flag = 0;Swap(&a[j], &a[j + 1]);}}if (flag == 1)//如果flag==1說明沒有進行交換則說明已經有序了break;}
}
(6) 快速排序
hoare版本
int GetMidi(int* a, int left, int right)
{int midi = (right - left) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else//a[left] > a[midi]{if (a[left] < a[right]){return left;}else if (a[midi] > a[right]){return midi;}else{return right;}}
}// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//三數取中,取中等的值作為基準值int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){//要保證keyi的值小于相遇位置,所以end先走while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[keyi]);//相遇位置與keyi交換此時這個位置就排好了return begin;
}
為了方便, 我們單獨將hoare版本寫為函數PartSort1,需要使用的時候直接調用
// 快速排序遞歸實現
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}//int keyi = left;//選取基準值//int begin = left, end = right;//begin找找大,end找小,然后交換//小區間優化,優化遞歸//if ((right - left + 1) < 10)//{// InsertSort(a + left,right - left + 1);//}//else//{// //三數取中,取中等的值作為基準值// int midi = GetMidi(a, left, right);// Swap(&a[left], &a[midi]);// int keyi = left;// int begin = left, end = right;// while (begin < end)// {// //要保證keyi的值小于相遇位置,所以end先走// while (begin < end && a[end] >= a[keyi])// {// end--;// }// while (begin < end && a[begin] <= a[keyi])// {// begin++;// }// Swap(&a[begin], &a[end]);// }// Swap(&a[begin], &a[keyi]);//相遇位置與keyi交換此時這個位置就排好了// keyi = begin;// QuickSort(a, left, keyi - 1);// QuickSort(a, keyi + 1, right);//}//int keyi = PartSort1(a, left, right);//int keyi = PartSort2(a, left, right);int keyi = PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}
挖坑版
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//三數取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;//先挖個坑,保存a[keyi]的值int tmp = a[keyi];while (begin < end){//讓對面先走,找小while (begin < end && a[end] >= a[keyi]){end--;}a[keyi] = a[end];keyi = end;while (begin < end && a[begin] <= a[keyi]){begin++;}a[keyi] = a[begin];keyi = begin;}//相遇之后把tmp填坑a[keyi] = tmp;return keyi;
}
前后指針版
// 快速排序前后指針法
int PartSort3(int* a, int left, int right)
{//三數取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;//定義前后指針,這樣不需要考慮是begin先走還是end先走//初始prev在前,cur在后一個位置,如果cur小于keyi則與++prev進行交換int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//如果在同一個位置就不需要交換{Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);return prev;
}
非遞歸版
可以使用隊列進行存儲區間
//非遞歸版
#include"stack.h"
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort1(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]//先壓入右區間if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}Destroy(&st);
}歸并排序
更多詳情點擊: 博客鏈接
歸并排序是一種經典的排序算法，它基于分治的思想。
歸并排序的時間復雜度是O(nlogn)，其中n是待排序數組的元素個數。
歸并排序是一種穩定的排序算法，適用于各種數據規模。它的主要缺點是需要額外的空間來存儲臨時數組。
(7) 歸并排序
遞歸版
void _MergeSort(int* a, int* tmp, int begin,int end)//傳遞區間遞歸調用
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int j = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}// 歸并排序遞歸實現
void MergeSort(int* a, int n)
{int* tmp = malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}非遞歸版
// 歸并排序非遞歸實現
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1; //11歸并while (gap < n){for (int i = 0; i < n; i += gap*2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int j = i;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);tmp = NULL;
}
線性時間比較類
(8) 計數排序
時間復雜度:O(N+range)
只適合整數/適合范圍集中
空間范圍度：O(range)
// 計數排序
void CountSort(int* a, int n)
{//找數的范圍int max = a[0], min = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;//需要開辟的空間大小int* count = (int*)calloc(range, sizeof(int));//malloc需要手動初始化,而calloc默認初始化為0if (count == NULL){perror("calloc fail");return;}//開始計數for (int i = 0; i < n; i++){count[a[i] - min]++;}//開始排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}free(count);
}
基數排序與桶排序
這兩種排序只需要稍作了解, 面試一般沒有.
基數排序是一種非比較排序算法，它根據數字的位數進行排序。基數排序的基本思想是將整數按照個位、十位、百位等位數進行排序，最終得到有序的結果。
基數排序的步驟如下：
首先找到待排序數組中的最大值，并確定其位數，記為max_digits。
創建10個桶，分別代表數字0-9。
從個位開始，將所有數字放入對應的桶中。
依次取出桶中的數字，并按照順序放回原數組中。
重復步驟3和步驟4，直到按照最高位排序完畢。
基數排序的時間復雜度為O(n*k)，其中n是待排序數組的長度，k是最大位數。需要注意的是，基數排序只適用于整數排序，且要求待排序數字必須是非負數。
桶排序是一種排序算法，它將數據按照一定的范圍劃分為多個桶，然后對每個桶中的數據進行排序，最后將每個桶中的元素按照順序依次取出來得到有序序列。
具體的桶排序算法如下：
創建一個定量的空桶數組。
遍歷輸入數據，并將每個元素放入對應的桶中。
對每個非空桶中的元素進行排序。
依次將非空桶中的元素取出，并放入輸出序列。
桶排序的時間復雜度取決于對每個桶中的元素進行排序的算法，通常采用的是快速排序或插入排序，所以整體的時間復雜度為O(n+k)，其中n為待排序序列的長度，k為桶的數量。
桶排序適用于數據分布較均勻的情況，當數據分布不均勻時，不同的桶中的數據量差別較大，可能會導致某些桶中的數據在排序后仍然不是有序的，因此對于不同的數據分布情況，桶的數量和每個桶的容量需要適當調整。
總結
穩定性 :三穩四不穩
穩定性指的是, 相同的值,其相對位置排序后保持不變,作用一般在排列結構體數據時,比如高考總分排列,但是總分相同,就按照語文成績高低排列, 此時可以使用穩定排序, 先排語文成績,在排總成績.
計數排序,基數排序和桶排序因為排列數據具有局限性,所以這里不探討其穩定性
選擇排序為什么不是穩定的?
比如下列情況
{ 6 , 1 , 1} 這種情況將第二個1換到前面, 相對位置不變
{ 6, 6, 1}但是這種情況相同的6卻因為選擇發生了變化, 所以是不穩定的.
為什么快速排序具有空間消耗?
因為遞歸會創建棧幀空間.
冒泡排序:
比較相鄰的元素，如果前一個比后一個大，則交換位置，直到將最大的元素移到最后。
時間復雜度：平均O(n^ 2)，最好情況O(n)，最壞情況O(n^2)。
選擇排序:
每次從未排序的元素中選擇最小的元素，放到已排序的末尾。
時間復雜度：平均O(n^ 2)，最好情況O(n^2)，最壞情況O(n ^2)。
插入排序:
將未排序的元素逐個插入到已排序的序列中的正確位置。
時間復雜度：平均O(n^ 2)，最好情況O(n)，最壞情況O(n^2)。
希爾排序:
根據間隔將序列劃分為多個子序列，對子序列進行插入排序，然后縮小間隔直至最后一次插入排序。
時間復雜度：平均O(n log n)，最好情況O(n log^ 2 n)，最壞情況O(n^2)。
歸并排序:
將序列遞歸地拆分成兩個子序列，然后將兩個有序子序列合并為一個有序序列。
時間復雜度：平均O(n log n)，最好情況O(n log n)，最壞情況O(n log n)。
快速排序:
選擇一個基準元素，將序列分為兩部分，小于基準的放在左邊，大于基準的放在右邊，然后遞歸地對兩個部分進行快速排序。
時間復雜度：平均O(n log n)，最好情況O(n log n)，最壞情況O(n^2)。
堆排序:
將序列構建成一個最大堆，然后不斷將堆頂元素與最后一個元素交換，并重新調整堆，直到所有元素都有序。
時間復雜度：平均O(n log n)，最好情況O(n log n)，最壞情況O(n log n)。
計數排序:
統計每個元素的出現次數，然后根據統計結果將元素放回原數組。
時間復雜度：平均O(n+k)，最好情況O(n+k)，最壞情況O(n+k)。
桶排序:
將元素分到不同的桶中，然后對每個桶進行排序，最后按順序將元素取出。
時間復雜度：平均O(n+k)，最好情況O(n)，最壞情況O(n^2)。
基數排序:
根據元素的位數依次進行排序，從最低位到最高位。
時間復雜度：平均O(nk)，最好情況O(nk)，最壞情況O(n*k)。
完
