🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。

前言：今天這篇文章主要是想給大家分享一下計數排序，并且對前面實現過的排序算法的時間復雜度，空間復雜度，穩定性進行一個歸納總結。話不多說，我們直接進入正文內容。

---

目錄

一.計數排序

核心步驟：

代碼實現：

計數排序的特性：?

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

各排序算法對比表：?

---

一.計數排序

計數排序（Counting Sort）又稱為鴿巢原理，是一種非比較型的線性時間排序算法，適用于 輸入數據范圍明確且較窄的場景。核心思想是通過“統計每個值的出現次數”，直接確定元素的最終位置，跳過耗時的比較操作。

核心步驟：

1. 確定數據范圍
遍歷數組，找到最大值 max 和最小值 min，計算數據范圍 range = max - min + 1。
（目的：創建合適大小的計數數組，避免空間浪費）

2. 統計元素出現次數
創建計數數組 count（長度為 range），注意count數組的初始化(開辟時用calloc或者后續用memset)，遍歷原數組，將每個元素 arr[i] 映射到 count[arr[i] - min]（減去 min 是為了處理包含負數的情況，一定要用arr[i]-min），統計每個值的出現次數。

3. 將count數組中的數據排序還原到原數組中

定義一個索引變量index，用于記錄原數組arr中即將寫入數據的位置。遍歷count數組(從0開始，然后小于<range)，根據count[i]統計到的個數進行循環，循環次數等于該值出現的次數，將數組的原始數據值放入arr原始數組中(對應原始值一定是i+min)

代碼實現：

//非比較排序--計數排序
void CountSort(int* arr, int n)
{//找最大最小值確定范圍int min = arr[0]; int max = arr[0];for (int i = 0; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(-1);}//對count初始化，可以用memset也可以前面申請空間的時候使用callocmemset(count, 0, sizeof(int) * range);//統計次數，映射，下標為arr[i]-minfor (int i = 0; i < n; i++){count[arr[i] - min]++;}//排序int index = 0;//用range就可以了for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;//這里需要用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 test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//直接插入排序//InsertSort(a, size);//希爾排序//ShellSort(a, size);//直接選擇排序//SelectSort(a, size);//堆排序//HeapSort(a, size);//冒泡排序//BubbleSort(a, size);//快速排序//QuickSort(a, 0, size - 1);//非遞歸快速排序//QuickSortNoare(a, 0, size - 1);//快速排序進階版//QuickSortMore(a, 0, size - 1);//歸并排序//MergeSort(a, size);//非遞歸實現歸并排序//MergeSortNore(a, size);//非比較排序--計數排序CountSort(a, size);printf("排序后:");PrintArr(a, size);
}int main()
{test1();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.h文件，在這里給大家看一看

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.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);//交換排序
//1)冒泡排序
void BubbleSort(int* arr, int n);
//2)快速排序
void QuickSort(int* arr, int left, int right);
//快速排序非遞歸版本
void QuickSortNoare(int* arr, int left, int right);
//快速排序進階版本
void QuickSortMore(int* arr, int left, int right);//歸并排序--主函數里面不遞歸，所以可以先不傳left和right
void MergeSort(int* arr, int n);
//非遞歸實現歸并排序
void MergeSortNore(int* arr, int n);//非比較排序--計數排序
void CountSort(int* arr, int n);

---

往期回顧：

【數據結構初階】--排序(一)：直接插入排序，希爾排序

【數據結構初階】--排序(二)--直接選擇排序，堆排序

【數據結構初階】--排序(三)：冒泡排序，快速排序

【數據結構初階】--排序(四)：歸并排序

結語：本篇博客就到此結束了，后續應該還會更新一篇歸并排序的進階，然后就正式進入C++的學習了。我們數據結構初階講這些數據結構都是用C語言實現的，還有些比較難的數據結構在后續C++的學習中我們也會接觸到，但是利用C++來實現就方便很多了，如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持。