文章目錄
- 直接插入排序
- 希爾排序
- 選擇排序
- 堆排序
- 冒泡排序
- 快速排序
- 快速排序hoare版本
- 快速排序遞歸挖坑版本
- 快速排序遞歸前後指針法
- 歸并排序
- 計數排序
在介紹排序算法之前，先在其他小夥伴裡找到一張排序算法時間複雜度，空間複雜度以及穩定性的總結圖檔(桶排序和基數排序先沒更新)，而排序算法中的穩定性是指，在排序過程後，這一組資料之間的相對位置不能發生改變，就比如說：1 2 5 2 5 3，排完序後不能把原本後面的5排到前面那個5的前面去。
- 插入類排序
-
直接插入排序
時間複雜度: O(n2)
空間複雜度: O(1)
穩定性: 穩定
直接插入排序是把待排的數字，從後向前，依次插入一段有序的序列中，直至序列全部有序。至于為什麼從後向前比較，是因為可以在比較的途中，直接把大數字向後挪移，就減少了周遊的時間，這種情況沒有什麼比用打牌來說明更好的了。
排序算法的多個版本直接插入排序希爾排序選擇排序堆排序冒泡排序快速排序快速排序hoare版本快速排序遞歸挖坑版本快速排序遞歸前後指針法歸并排序計數排序
// 插入排序
void InsertSort(int* a, int n)
{
int i = 0;
//i表示目前需要插入的數字的下标
for (i = 1; i < n; i++)
{
int end = i - 1;//需要比較的數字的下标
int tmp = a[i];//需要插入的數字
while (end >= 0)
{
//如果前面的數比較大，把大數向後挪
if (a[end] > tmp)
{
a[end + 1] = a[end];
}
else
{
//找到第一個小于或等于後面數的位置就退出循環
break;
}
end--;
}
a[end + 1] = tmp;
}
}
-
希爾排序
時間複雜度：O(n logn) ~O(n2)
空間複雜度: O(1)
穩定性: 不穩定
希爾排序又稱為縮小增量排序，先標明一個距離，然後把所有間隔為該距離的數想成一組，對改組資料進行排序，重複該操作，直至距離為1，整個序列有序了。
// 希爾排序
void ShellSort(int* a, int n)
{
//預排序 間距為gap 的插入排序
int gap = n;
//gap != 1 -->預排序階段
//gap == 1 --> 排序階段
while (gap != 1)
{
gap = gap / 3 + 1; //定義每次排序的間距
int j = 0;
for (j = 0; j < n - gap; j++)
{
int end = j ;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = tmp;
}
}
}
- 選擇類排序
-
選擇排序
時間複雜度:O(n2)
空間複雜度：O(1)
穩定性: 不穩定
選擇排序有兩種寫法，一種是隻從一邊出發，每次找到目前無序數組中最大或者最小的，然後放在最後；另一種是從兩邊出發，每次找到目前數組最大和最小的數字，然後放在兩邊。(這裡需要小心，如果說最大數在最左邊，那麼先交換最小數，可能會出現最大數不在記錄的位置)
eg： 8 1 3 5 2 4
第一遍找完，發現min = 1,max = 0(該數字的下标)
然後先把min 放到 0号下标的位置，就變成了
1 8 3 5 2 4
緊接着再把max 放到 5 号末尾，按照下标交換的結果就是
4 8 3 5 2 1
就跟我們預期的結果不同，這種情況需要單獨處理。
// 選擇排序
void SelectSort(int* a, int n)
{
int i = 0;
int j = 0;
for (j = 0; j < n / 2; j++)
{
int min = j, max = j;
for (i = j; i < n - j; i++)
{
if (a[i] > a[max])
{
max = i;
}
else if (a[i] < a[min])
{
min = i;
}
}
Swap(a, j, min);
//處理沖突的情況
if (j == max)
{
max = min;
}
Swap(a, n - j - 1, max);
}
}
-
堆排序
時間複雜度：O(n log(n))
空間複雜度：O(1)
穩定性: 不穩定
在進行堆排序時，首先得知道堆這個概念
堆分為兩種，一種是大根堆，一種是小根堆。根節點最大的堆叫做最大根堆或大根堆，根節點最小的堆叫做最小根堆或小根堆。
堆的特征: 堆中每個節點的值總是不大于或不小于其父親節點的值；堆總是一顆完全二叉樹。既然是完全二叉樹，那麼堆可以用數組來存儲。
而在堆排序中，想要按照升序來排列，需要建大堆；按照降序排列需要建小堆。
如果是升序排列，根節點的值永遠為目前堆的最大值，我們每次就可以交換目前無序數組兩端的數字，然後再向下建堆(此時無序數組長度 -1)，這樣就可以每次把最大值放到有序的位置。
應用：平常玩王者榮耀的時候，旁邊總會有一個全區前100，排位前多少名的序列，這個時候，表中隻需要前100名，總不可能每次更新排名的時候，都把所有玩家排個序，然後取前100名玩家。
這個時候就可以通過建立一個100個資料的小根堆，此時根節點為目前的最小值，然後隻要後面的資料比根節點大，就交換根節點和改資料的值，再向下建堆，增加了效率。(廣告加的一點也不生硬)
// 堆排序
//向下建立大根堆
//a 是堆的數組 n 是無序數組的長度 root 需要建堆的根節點
void AdjustDwon(int* a, int n, int root)
{
int parent = root;//父親節點
int child = root * 2 + 1;//左孩子節點（因為數組的起始位置是 0 ，是以需要 +1）
while (child < n)
{
//先選擇出父親節點的左右孩子節點比較大的一個節點
if (child < (n - 1) && a[child] < a[child + 1])
{
child++;
}
if (a[parent] < a[child])
{
//如果父親節點值小于孩子節點，交換兩值
Swap(a, parent, child);
parent = child;
child = parent * 2 + 1;
}
else
{
//如果父親節點大于孩子節點，就不需要再判斷了，大根堆的每一個根節點都是一個大根堆。
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
int i = 0;
//先建立一個大根堆，向下調整法
for (i = n / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
//排序
for (i = n - 1; i > 0; i--)
{
Swap(a, 0, i);
AdjustDwon(a, i, 0);
}
}
- 交換類排序
-
冒泡排序
時間複雜度：O(n2)
空間複雜度：O(1)
穩定性：穩定
冒泡排序作為我們平常使用最多的排序，代碼簡潔，不容易出錯，還能解決很多不是大資料的問題，這裡就不做解釋了代碼不香嗎
void Bubbing(int* a,int len)
{
int i=0;
int j=0;
for(i=1;i<len;i++)
{
int flag = 1;
for(j=0;j<len-i;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
flag = 0;
}
}
//如果沒發生交換，說明所有序列都是有序的，不需要再繼續下去了
if(flag)
{
break;
}
}
}
-
快速排序
時間複雜度：O(n log(n)) ~ O(n2)
空間複雜度：O(log(n)) (遞歸調用函數，開辟棧幀消耗空間)
穩定性：不穩定
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼将待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然後最左右子序列重複該過程，直到所有元素都排列在相應位置上為止。
快速排序的三總形式：hoare版本，挖坑法，前後指針版本
快速排序的優化：三數取中，随機數法(排序速度選擇權交給上帝)
快速排序在排序中，如果目前序列本身就是有序的，那麼快速排序的時間複雜度就到最壞的情況，即O(n2)，想要讓快速排序排的越快，就跟我們的選值有關，如果我們讓選的值最後都在目前序列的中間位置，就可以讓他的速度相對來說快一點(三數取中)。
三數取中，随機數法
void choose(int* a,int left,int right)
{
//随機數法
//int key = left + rand()%(right - left);
//三數取中
int key = (left + right) / 2;
if (a[left] < a[key])
{
if (a[key] < a[right])
{
Swap(a, left, key);
}
else
{
if (a[left] < a[right])
{
Swap(a, left, right);
}
}
}
else
{
if (a[key] > a[right])
{
Swap(a, left, key);
}
else
{
if (a[left] > a[right])
{
Swap(a, left, right);
}
}
}
}
遞歸版本
快速排序hoare版本
如果第一個數選的是最左邊的數，那麼就先從右邊開始找第一個比他小的，再從左邊找第一個比他大的，然後交換這兩個數的位置，持續這樣做，直到兩指針相遇，再交換最左邊和相遇點的資料。
// 快速排序hoare版本
void PartSort1(int* a, int left, int right)
{
//遞歸結束條件
if (left >= right)
{
return;
}
//快速排序的優化，三數取中，随機數法
choose(a,left,right);
int key = left;
int l = left;
int r = right;
while (left < right)
{
//找到從右向左第一個小于 a[key] 的值
while (left < right && a[right] >= a[key])
{
right--;
}
//找到從左往右第一個大于 a[key] 的值
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(a, left, right);
}
Swap(a, left, key);
PartSort1(a, l, left - 1);
PartSort1(a, left + 1, r);
}
快速排序遞歸挖坑版本
挖坑法呢，顧明思議，排序前先在選擇的位置留下一個坑，隻要找到一個不符合的數，就用這個數來填坑，然後這個數原本的位置就變成了一個坑，留到最後給終止位置填坑。
// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
//遞歸結束條件
if (left >= right)
{
return;
}
choose(a, left, right);
int key = a[left];
int l = left;
int r = right;
while (left < right)
{
//找到從右向左第一個小于 a[key] 的值
while (left < right && a[right] >= key)
{
right--;
}
a[left] = a[right];
//找到從左往右第一個大于 a[key] 的值
while (left < right && a[left] <= key)
{
left++;
}
a[right] = a[left];
}
a[left] = key;//填坑
PartSort1(a, l, left - 1);
PartSort1(a, left + 1, r);
}
快速排序遞歸前後指針法
這個方法的思路就跟用O(n)的時間複雜度，把一個序列中偶數放在前面，奇數放在後面一樣。
// 快速排序前後指針法
void PartSort3(int* a, int left, int right)
{
//遞歸結束條件
if (left >= right)
{
return;
}
int prev = left - 1;
int cur = left;
int key = a[left];
int i = 0;
while (cur <= right)
{
if (a[cur] < key)
{
Swap(a, ++prev, cur);
}
cur++;
}
PartSort1(a, left, prev - 1);
PartSort1(a, prev + 1, right);
}
非遞歸版本
首先呢，遞歸版本其實是利用函數調用開辟的棧幀來儲存資料，棧幀的本質還是棧，先進後出，我們就可以利用棧來改成非遞歸的版本，感覺就像是一個換了名字的深度優先搜尋。
// 快速排序 非遞歸實作
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
//入棧方式 先入目前區間的左邊，再入右邊
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
//彈棧時，先得到的是區間的右邊，後得到左邊
right = StackTop(&st);
StackPop(&st);
left = StackTop(&st);
StackPop(&st);
//去除隻有一個數或者沒有數的情況的情況
if (left >= right)
{
continue;
}
int key = left;
int l = left;
int r = right;
while (left < right)
{
//找到從右向左第一個小于 a[key] 的值
while (left < right && a[right] >= a[key])
{
right--;
}
//找到從左往右第一個大于 a[key] 的值
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(a, left, right);
}
Swap(a, left, key);
//先讓右邊區間入棧
StackPush(&st, left+1);
StackPush(&st, r);
//左邊區間入棧
StackPush(&st, l);
StackPush(&st, left - 1);
}
StackDestroy(&st);
}
- 歸并類排序
-
歸并排序
時間複雜度：O(n log(n))
空間複雜度：O(n)
穩定性：穩定
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并
void _MergeSort(int* a, int* tmp, int left, int right)
{
int mid = (left + right) / 2;
/*
[0,7] -> [0,3] [4,7]
遞歸[0,3] -> 劃分[0,1][2,3]
遞歸[0,1] ->劃分[0,0][1,1] -->歸并出有序的 [0,1]
遞歸[2,3] ->劃分[2,2][3,3] -->歸并出有序的 [2,3]
[0,1][2,3] --> 歸并出有序的[0,3]
遞歸[4,7] -> 劃分[4,5][5,7]
遞歸[4,5] ->劃分[4,4][5,5] -->歸并出有序的 [4,5]
遞歸[6,7] ->劃分[6,6][7,7] -->歸并出有序的 [6,7]
[4,5] [6,7] --> 歸并出有序的[4,7]
[0,3] [4,7] --> 歸并出有序的[0,7]
*/
if (left >= right)
{
return;
}
//[left,mid] [mid+1,right]
_MergeSort(a, tmp, left, mid);
_MergeSort(a, tmp, mid + 1, right);
//兩個有序數組的合并
int begin1 = left, begin2 = mid + 1;
int end1 = mid, end2 = right;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
//将tmp排序好的資料拷貝到a數組對應位置
memcpy(a + left, tmp + left, sizeof(int)* (right - left + 1));
}
// 歸并排序遞歸實作
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)* n);
_MergeSort(a, tmp, 0, n - 1);
}
非遞歸版本
// 歸并排序非遞歸實作
void MergeSortNonR(int* a, int n)//n為數組裡元素的數量
{
int* tmp = (int*)malloc(sizeof(int)* n);
int size = 1;
int count = (int)(log(n) / log(2)) + 1;;
for (; size < n;size *= 2)
{
int i = 0;
for (i = 0; i < n; i += size*2)
{
int left = i, mid = i + size,right = mid + size;
//處理最後一組不滿足size個大小的情況
if (mid > n)
{
mid = n;
}
if (right > n)
{
right = n;
}
//兩個有序數組的合并
//[begin1,end1) [begin2,end2)
int begin1 = left, begin2 = mid;
int end1 = mid, end2 = right;
int index = begin1;
while (begin1 < end1 && begin2 < end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 < end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 < end2)
{
tmp[index++] = a[begin2++];
}
}
// 将tmp排序好的資料拷貝到a數組對應位置
memcpy(a, tmp, sizeof(int)* n);
}
free(tmp);
}
- 非比較類排序
-
計數排序
時間複雜度：O(max(n,範圍))
空間複雜度：O(範圍)
穩定性：穩定
計數排序需要先找到目前數組的最大值和最小值，然後通過一個輔助空間，把最大值和最小值壓縮在一個輔助數組中，如果最大值和最小值之間差距比較大，而且資料還是那種稀疏矩陣類型的，是用計術排序就顯得不那麼好。
// 計數排序(非比較類)
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
//先找到數組中最大值和最小值
int i = 0;
for (i = 0; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
if (min > a[i])
{
min = a[i];
}
}
//資料所在的一個範圍
int range = max - min + 1;
int* arr = (int*)calloc(range,sizeof(int));
//統計對應的資料出現的次數
for (i = 0; i < n; i++)
{
int tmp = a[i] - min;
arr[tmp]++;
}
int len = 0;
//根據次數排序，傳回原數組
for (i = 0; i < range; i++)
{
while (arr[i])
{
a[len++] = i + min;
arr[i]--;
}
}
free(arr);
}