😘個人主頁：@Cx330?
👀個人簡介：一個正在努力奮斗逆天改命的二本覺悟生
📖個人專欄：《C語言》《LeetCode刷題集》《數據結構-初階》
前言：今天這篇博客就給大家將一個計數排序，然乎就給大家總結一下所有的排序算法的時間復雜度，空間復雜度，穩定性進行一個歸納總結。
目錄
一、計數排序
核心步驟：
代碼實現：
測試結果：
計數排序的特性：
二.排序算法復雜度及穩定性分析
各排序算法對比表：
代碼展現：
Sort.c:
Sort.h:
test.c:
一、計數排序
計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。
思路：
- 統計相同元素出現次數
- 根據統計的結果將序列回收到原來的序列中
核心步驟：
1. 確定數據范圍
遍歷數組，找到最大值和最小值，然后計算數據范圍range=max-min+1確定數組的空間（避免空間浪費）
2. 統計元素出現次數
創建一個計數數組count，空間大小為range，并且要給count初始化（calloc或者memset），遍歷原數組，將每個元素 arr[i] 映射到 count[arr[i] - min]（減去 min 是為了處理包含負數的情況，一定要用arr[i]-min），統計每個值的出現次數。
3. 將count數組中的數據排序還原到原數組中
再定義一個index變量，作為原數組的下標，遍歷count數組，根據count[i]統計到的個數進行映射i+min就是原數組的值，循環次數等于該值出現的次數，將數組的原始數據值放入arr原始數組中(對應原始值一定是i+min)
代碼實現：
//非比較排序--計數排序
void CountSort(int* arr, int n)
{int min = arr[0], max = arr[0];for (int i = 0; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//確定count數組大小int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}//對count初始化memset(count, 0, sizeof(int) * range);for (int i = 0; i < n; i++){count[arr[i] - min]++;}//將count數組映射到arr數組中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min ;}}
}test.c:
#include"Sort.h"
void printArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test01()
{int a[] = { 5,3,9,6,2,4,7,1,8 };//int a[] = { 6,1,2,7,9,3 };int n = sizeof(a) / sizeof(a[0]);printf("排序之前：");printArr(a, n);//InsertSort(a, n);//ShellSort(a, n);//SelectSort(a, n);//HeapSort(a, n);//BubbleSort(a, n);//QuickSort(a, 0, n - 1);//QuickSortNorR(a, 0, n - 1);//MergeSort(a, n);CountSort(a, n);//MergeSortNonR(a, n);printf("排序之后：");printArr(a, n);
}void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{test01();//TestOP();return 0;
}測試結果：
測試完成，打印沒有問題，升序排序正確，退出碼為0?
計數排序的特性：
- 計數排序在數據范圍集中時，效率很高，但是適用范圍以及場景有限
- 時間復雜度：O(n+range)
- 空間復雜度：O(range)
- 穩定性：穩定
二.排序算法復雜度及穩定性分析
穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
各排序算法對比表：
其中冒泡排序，直接插入排序，歸并排序是穩定的，這里就不過多介紹了，我們主要通過一些特例來看下那些不穩定的排序算法。至于時間復雜度和空間復雜度，博主大部分都在前面的博客中分享過了。
1.直接選擇排序：
2.希爾排序：
3.堆排序：
4.快速排序：
代碼展現：
Sort.c:
#include"Sort.h"
#include"stack.h"
//1）直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}//2)希爾排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tmp;}}
}void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
//向下調整
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){ //找大的孩子//建大堆 <//建小堆 >if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//孩子和父親比較//建大堆 <//建小堆 >if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* arr, int n)
{//向下調整算法--建堆 時間復雜度O(n）for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);//因為這里建的是小堆，所以向下調整，就成了降序}//向上調整算法--建堆 時間復雜度O(n*logn)/*for (int i = 0; i < n; i++){AdjustUp(arr, i);}*///n* lognint end = n - 1;while (end > 0)//循環取最后一個元素與頂交換，再向下調整{Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}//冒泡排序
void BubbleSort(int* arr, int n)
{int change = 1;for (int i = 0; i < n-1; i++){for (int j = 0; j < n - 1 - i; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);change = 0;}}if (change == 1){break;}}
}//1）直接選擇排序
//void SelectSort(int* arr, int n)
//{
// for (int i = 0; i < n; i++)
// {
// int mini = i;
// for (int j = i + 1; j < n; j++)
// {
// if (arr[j] < arr[mini])
// {
// mini = j;
// }
// }
// Swap(&arr[mini], &arr[i]);
// }
//}//直接選擇排序
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin+1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//交換if (begin == maxi){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}
}//找基準值--hoare版本
int _QuickSort1(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){//right從右往左找比基準值小的，如果大于基準值就--while (left <= right && arr[right] > arr[keyi]){--right;}//left從左往右找比基準值大的，如果小于基準值就++while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交換if(left<=right)Swap(&arr[left++], &arr[right--]);}//right位置就是基準值的位置Swap(&arr[right], &arr[keyi]);return right;
}//找基準值--挖坑法
int _QuickSort(int* arr, int left, int right)
{int hole = left;int key = arr[hole];while (left < right){while (left<right && arr[right] > key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < key){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}//找基準值--lumoto雙指針法
int _QuickSort2(int* arr, int left, int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur < right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}++cur;}Swap(&arr[prev], &arr[keyi]);return prev;
}//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基準值keyiint keyi = _QuickSort(arr, left, right); //左序列[left,keyi-1]右序列[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}//找基準值非遞歸版--棧
void QuickSortNorR(int* arr, 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);//[begin,end]--找基準值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDesTroy(&st);
}void _MergeSort(int* arr, int left, int right,int*tmp)
{//分解if (left >= right){return;}//根據mid將[left,right]劃分為左右兩個序列[left,mid] [mid+1,right]int mid = left + (right - left) / 2;_MergeSort(arr, left, mid,tmp);_MergeSort(arr, mid+1, right,tmp);//合并[left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid+1, end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//要么begin1越界 //要么begin2越界while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){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);//[0,n-1]_MergeSort(arr, 0, n - 1,tmp);free(tmp);tmp = NULL;
}//非比較排序--計數排序
void CountSort(int* arr, int n)
{int min = arr[0], max = arr[0];for (int i = 0; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//確定count數組大小int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}//對count初始化memset(count, 0, sizeof(int) * range);for (int i = 0; i < n; i++){count[arr[i] - min]++;}//將count數組映射到arr數組中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min ;}}
}//歸并排序--非遞歸版本
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!\n");exit(1);}int gap = 1;while (gap < n){//根據gap劃分組，兩兩合并for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = begin1;//處理奇數個數據if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//合并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 + i, tmp+i, sizeof(int)*(end2 - i + 1));}gap *= 2;}free(tmp);
}Sort.h:
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<time.h>
//插入排序
//1）直接插入排序
void InsertSort(int* arr, int n);
//2)希爾排序
void ShellSort(int* arr, int n);//選擇排序
//1）直接選擇排序
void SelectSort(int* arr, int n);
//2）堆排序
void HeapSort(int* arr, int n);
//冒泡排序
void BubbleSort(int* arr, int n);
//快速排序
void QuickSort(int* arr, int left, int right);
//找基準值非遞歸版--棧
void QuickSortNorR(int* arr, int left, int right);
//歸并排序--遞歸版本
void MergeSort(int* arr, int n);
//非比較排序--計數排序
void CountSort(int* arr, int n);
//歸并排序--非遞歸版本
void MergeSortNonR(int* a, int n);test.c:
#include"Sort.h"
void printArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test01()
{int a[] = { 5,3,9,6,2,4,7,1,8 };//int a[] = { 6,1,2,7,9,3 };int n = sizeof(a) / sizeof(a[0]);printf("排序之前：");printArr(a, n);//InsertSort(a, n);//ShellSort(a, n);//SelectSort(a, n);//HeapSort(a, n);//BubbleSort(a, n);//QuickSort(a, 0, n - 1);//QuickSortNorR(a, 0, n - 1);//MergeSort(a, n);CountSort(a, n);//MergeSortNonR(a, n);printf("排序之后：");printArr(a, n);
}void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{test01();//TestOP();return 0;
}往期回顧：
【數據結構初階】--排序(一)：直接插入排序，希爾排序
【數據結構初階】--排序（二）：直接選擇排序，堆排序
【數據結構初階】--排序（三）：冒泡排序、快速排序
【數據結構初階】--排序（四）：歸并排序
總結：這篇博客到此為止，排序的數據結構就已經全部寫完了，數據結構初階也就結束了，后續我還會寫一些某些排序的進階，然后就正式進入C++的學習了。我們數據結構初階講這些數據結構都是用C語言實現的，還有些比較難的數據結構在后續C++的學習中我們也會接觸到，但是利用C++來實現就方便很多了，如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持。
API)
