前言

? ? ? ? 所謂排序，就是將一組數(shù)據(jù)按照遞增或者遞減的方式進(jìn)行排列，讓這組數(shù)據(jù)變得有序起來(lái)。排序在生活中運(yùn)用的是十分廣泛的，各行各業(yè)都用到了排序，比如我們?cè)诰W(wǎng)購(gòu)的時(shí)候就是按照某種排序的方式來(lái)選擇東西的。所以去了解排序的實(shí)現(xiàn)也就是很重要的了。

目錄

1.排序的概念

2.常見(jiàn)的排序算法

3.常見(jiàn)的排序算法的實(shí)現(xiàn)

? ? ? ? 3.1插入排序

????????????????3.1.1直接插入排序?

? ? ? ? ? ? ? ? 3.1.2希爾排序?

? ? ? ? 3.2選擇排序

? ? ? ? ? ? ? ? 3.2.1堆排序

? ? ? ? ? ? ? ? 3.2.2直接選擇排序??

? ? ? ? 3.3交換排序

? ? ? ? ? ? ? ? 3.3.1冒泡排序

? ? ? ? ? ? ? ? 3.3.2快速排序?

? ? ? ? 3.4歸并排序

? ? ? ? ? ? ? ? 3.4.1歸并排序?

? ? ? ? ? ? ? ? 3.4.2歸并排序應(yīng)用-外排序

? ? ? ? 3.5非比較排序?

4.排序算法的復(fù)雜度及穩(wěn)定性的分析??

---

1.排序的概念

? ? ? ? 排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小按照一定的規(guī)律變成遞增或者遞減的序列。

? ? ? ? 穩(wěn)定性：?假定待排序的記錄序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序后這些記錄的相對(duì)次序沒(méi)有發(fā)生變化，即在原序列中r[i] = r[j],且r[i]在r[j]之前，而在排序后r[i]任在r[j]之前，則稱這種排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。

? ? ? ? 內(nèi)排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

? ? ? ? 外排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程中的要求能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

2.常見(jiàn)的排序算法

?????????

3.常見(jiàn)的排序算法的實(shí)現(xiàn)

? ? ? ? 3.1插入排序

? ? ? ? 基本思想：把待排序的記錄按其關(guān)鍵碼值逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的序列插完為止，得到一個(gè)新的有序序列。

? ? ? ? 實(shí)際上我們?cè)谕鎿淇伺诺臅r(shí)候，就用到了插入排序的思想。

?????????

????????????????3.1.1直接插入排序?

? ? ? ? 當(dāng)插入第i個(gè)元素的時(shí)候前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用arryy[i]的排序碼與array[i -1],array[i-2],array[i-3],...的排序碼順序比較找到插入的位置即將array[i]插入，原來(lái)位置上的元素順序后移。

? ? ? ? 比較過(guò)程，如果是排升序，先與當(dāng)前值比較，如果比當(dāng)前值小就和當(dāng)前值的前一個(gè)元素比較，如果比當(dāng)前值的前一個(gè)元素大，就插入到當(dāng)前值的前一個(gè)元素的后面，如果比當(dāng)前值的前一個(gè)元素小，繼續(xù)去前面進(jìn)行比較，知道找到合適的位置進(jìn)行插入，如果是最小的，那么就要插入到數(shù)組的開(kāi)頭。如圖：

void InsertSort(int* a, int n)//升序排序
{assert(a);for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];//保存數(shù)據(jù)，后面移動(dòng)的時(shí)候數(shù)據(jù)會(huì)被覆蓋while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];//將數(shù)據(jù)向后移動(dòng)空出位置--end;//迭代繼續(xù)向前比較}else{break;//插入到}}a[end + 1] = tmp;}
}

? ? ? ? 直接插入排序的特性總結(jié)：

? ? ? ? 1.時(shí)間復(fù)雜度為O(N*2)。

? ? ? ? 2.排序的序列越接近有序，時(shí)間復(fù)雜度越低。

? ? ? ? 3.穩(wěn)定性：穩(wěn)定。

? ? ? ? 4.空間復(fù)雜度O(1)，它是一種穩(wěn)定的排序。

? ? ? ? 實(shí)現(xiàn)代碼：

? ? ? ? ? ? ? ? 3.1.2希爾排序?

? ? ? ? 希爾排序又稱縮小增量排序法。希爾排序的基本思想是：先選定一個(gè)整數(shù)，把待排序的文件中所記錄分成一個(gè)個(gè)組，所有距離為gap的記錄在一個(gè)組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，重復(fù)上述分組和排序的工作。當(dāng)gap = 1時(shí)，所以記錄統(tǒng)一排好序。

? ? ? ? 說(shuō)白了，希爾排序從直接插入排序找突破口，雖然直接插入排的時(shí)間復(fù)雜度很高，但是直接插入排序在有序或者接近有序的情況下，效率會(huì)是很好的，那么怎么樣讓它接近有序呢？這就要采用預(yù)排序了。通過(guò)預(yù)排序讓數(shù)組接近有序，最后一次在進(jìn)行直接插入排序，就會(huì)很快，通過(guò)這樣的方式?希爾排序?qū)χ苯硬迦肱判蜻M(jìn)行了很好的優(yōu)化。

? ? ? ? 希爾排序分為兩步：

????????1.對(duì)數(shù)組進(jìn)行預(yù)排序

? ? ? ? 將數(shù)組按照間隔gap分為很多組，先對(duì)間隔為gap的組進(jìn)行排序，使得間隔為gap的是有序的，然后縮小間隔gap。在重復(fù)上述過(guò)程。?

? ? ? ? 2.直接插入排序

? ? ? ? 當(dāng)gap等于1時(shí)，就相當(dāng)于是直接插入排序啦，聽(tīng)起來(lái)是不是很簡(jiǎn)單啊，hhhh。

?

????????如圖：

????????

//希爾排序
void ShellSort(int* a, int n)
{assert(a);//確保指針不為空int gap = n;while (gap > 1){gap = gap / 3 + 1;//保證最后一次排序的間隔是1，進(jìn)過(guò)計(jì)算gap按照三分之一減少是最優(yōu)的for (int i = 0; i < n - gap; ++i)//排升序{int end = i;int tmp = a[end + gap];//防止數(shù)據(jù)被覆蓋while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];//移動(dòng)數(shù)組，繼續(xù)在前面比較end = end - gap;}else{break;}}a[end + gap] = tmp;//將數(shù)據(jù)插入到數(shù)組中}Print(a, 10);printf("  gap = %d\n", gap);printf("\n");}}

? ? ? ? 希爾排序的特性總結(jié)

? ? ? ? 1.希爾排序是對(duì)直接插入排序的優(yōu)化。

? ? ? ? 2.?當(dāng)gap大于1的時(shí)候都是預(yù)排序，目的是讓數(shù)組更接近有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序了，這樣就可以很快的排出來(lái)了。這樣的話整體而言可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。

? ? ? ? 3.希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值有很多方法，導(dǎo)致很難去計(jì)算，因此在很多書里面希爾排序的時(shí)間復(fù)雜度都不固定。

?

? ? ? ? 因?yàn)檫@里的gap是按照Knuth的方法取值的，所以暫時(shí)按照來(lái)計(jì)算。

?????????

? ? ? ? 3.2選擇排序

? ? ? ? 基本思想：每次從待排序的數(shù)據(jù)中選出最小（或者最大的元素），存放到序列的起始位置，直到待排序的數(shù)組排序完為止。?

? ? ? ? ? ? ? ? 3.2.1堆排序

? ? ? ? 詳見(jiàn)：堆排序?

? ? ? ? ? ? ? ? 3.2.2直接選擇排序??

?????????排升序：在元素集合array[i]-array[n-1],選擇關(guān)鍵碼子最大（最小）的數(shù)據(jù)元素。

? ? ? ? 若它不是這組元素中的最后一個(gè)?（第一個(gè)）元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換。

? ? ? ? 在剩余的array[i]--array[n -2](array[i+1] --array[n-1])集合中重復(fù)上述步驟，直到集合剩下一個(gè)元素。

void SelectSort(int* a, int n)
{assert(a);//確保a存在//排升序int left = 0;int right = n - 1;while (left < right){int maxDex = right;int minDex = left;//遍歷剩余的數(shù)組每次找出最大的和最小的將最大的換到n-1的位置，將最小的放到j(luò)位置for (int i = left; i <= right; ++i){if (a[maxDex] < a[i] ){maxDex = i;//記錄最大值的下標(biāo)}if (a[minDex] > a[i]  ){minDex = i;//記錄最小值的下標(biāo)}}Swap(&a[minDex], &a[left]);if (left == maxDex)//說(shuō)明最大值的下標(biāo)在最左邊，上一步的交換讓最大值已經(jīng)不是最左邊，而是下標(biāo)minDexmaxDex = minDex;Swap(&a[maxDex], &a[right]);left++;right--;}
}

? ? ? ? ?它的時(shí)間復(fù)雜度是O（n*n）。

void SelectSort(int* a, int n)
{assert(a);//確保a存在//排升序int left = 0;int right = n - 1;while (left < right){int maxDex = right;int minDex = left;//遍歷剩余的數(shù)組每次找出最大的和最小的將最大的換到n-1的位置，將最小的放到j(luò)位置for (int i = left; i <= right; ++i){if (a[maxDex] < a[i] ){maxDex = i;//記錄最大值的下標(biāo)}if (a[minDex] > a[i]  ){minDex = i;//記錄最小值的下標(biāo)}}Swap(&a[minDex], &a[left]);if (left == maxDex)//說(shuō)明最大值的下標(biāo)在最左邊，上一步的交換讓最大值已經(jīng)不是最左邊，而是下標(biāo)minDexmaxDex = minDex;Swap(&a[maxDex], &a[right]);left++;right--;}
}

? ? ? ? 3.3交換排序

? ? ? ? ? ? ? ? 3.3.1冒泡排序

? ? ? ? 詳見(jiàn)?冒泡排序

? ? ? ? ? ? ? ? 3.3.2快速排序?

? ? ? ? 詳見(jiàn)快速排序?

? ? ? ? 快速排序除了遞歸的實(shí)現(xiàn)方法外，還有非遞歸的實(shí)現(xiàn)方法，那么，如何通過(guò)非遞歸來(lái)實(shí)現(xiàn)快排的呢？?讓我們一起來(lái)試試吧，我們都知道遞歸的方法實(shí)現(xiàn)快排是通過(guò)函數(shù)調(diào)用棧幀來(lái)實(shí)現(xiàn)的，其實(shí)非遞歸也是通過(guò)模擬函數(shù)調(diào)用棧幀的過(guò)程，通過(guò)數(shù)據(jù)結(jié)構(gòu)的棧來(lái)模擬實(shí)現(xiàn)的。

? ? ? ? 雖然數(shù)據(jù)結(jié)構(gòu)的棧和操作系統(tǒng)的棧不是一會(huì)事情，但是它們的性質(zhì)是相同的（后進(jìn)先出），如何通過(guò)棧來(lái)模擬實(shí)現(xiàn)呢？

? ? ? ? 代碼：?

// 快速排序 非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a, int begin, int end)
{//創(chuàng)建并初始化棧Stack st;StackInit(&st);//將區(qū)間[left,right]入棧StackPush(&st, end);StackPush(&st, begin);//通過(guò)棧來(lái)模擬快排遞歸時(shí)的調(diào)用//數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的棧和操作系統(tǒng)的棧的特性是一樣的while (!StackEmpty(&st)){int left = StackTop(&st);StackPop(&st);int right = StackTop(&st);StackPop(&st);//如棧的時(shí)候先右后左，出棧的時(shí)候先左后右int midi = PartSort1(a, left, right);//對(duì)子區(qū)間進(jìn)行快速排序的單趟排序//將左右子區(qū)間都入棧if (midi + 1 < right)//右邊區(qū)間至少存在一個(gè)數(shù){StackPush(&st, right);StackPush(&st, midi + 1);}if (left < midi - 1)//左邊區(qū)間至少存在一個(gè)數(shù){StackPush(&st, midi - 1);StackPush(&st, left);}}StackDestory(&st);
}

? ? ? ? 3.4歸并排序

? ? ? ? ? ? ? ? 3.4.1歸并排序?

? ? ? ? ? ? ? ? ?歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個(gè)典型應(yīng)用，將已經(jīng)有序的子序列合并，得到完全有序的的序列；即先使每個(gè)子序列都有序，在合并子序列使得整個(gè)區(qū)間有序，若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并，歸并排序的核心步驟：

代碼：

//單趟歸并排序
void _MergeSortSignal(int *a, int begin1, int end1, int begin2, int end2, int *tmp)//閉區(qū)間
{int begin = begin1;//保存數(shù)組起始的位置方便拷貝tmp = (int*)malloc(sizeof(int) * (10 + 1));int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//將剩下的一個(gè)數(shù)組尾插到tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = begin ; j <= end2; ++j){a[j] = tmp[j];}free(tmp);}
// 歸并排序遞歸實(shí)現(xiàn)
void _MergeSort(int* a, int left, int right, int * tmp)
{if (left >= right)//區(qū)間只剩下一個(gè)數(shù){return;}int midi = (left + right) / 2;_MergeSort(a, left, midi, tmp);_MergeSort(a, midi + 1, right, tmp);//合并有序的小區(qū)間_MergeSortSignal(a, left, midi, midi + 1, right, tmp);}
void MergeSort(int* a, int n)
{//int* tmp = (int*)malloc( sizeof(int) * n);_MergeSort(a, 0, n - 1,NULL);//閉區(qū)間[left,right]//free(tmp);
}

?

? ? ? ? 歸并排序的非遞歸法：?

? ? ? ? 如果采用棧來(lái)模擬會(huì)將問(wèn)題變得復(fù)雜，通過(guò)上面的圖，我們不難發(fā)現(xiàn)歸并排序是將要排序的區(qū)間不斷縮小的過(guò)程直到要排序的區(qū)間變得有序，那么怎么樣是一定有序的呢，我們不難發(fā)現(xiàn)，如果區(qū)間只有一個(gè)數(shù)的時(shí)候一定是有序的，所以我們采取這個(gè)思路，剛開(kāi)始讓相鄰的連個(gè)數(shù)進(jìn)行歸并，此時(shí)間隔gap為一，下一次，相鄰的兩個(gè)數(shù)已經(jīng)有序了，那么此時(shí)要將區(qū)間長(zhǎng)度為2的相鄰的兩個(gè)子區(qū)間歸并為一個(gè)有序的區(qū)間，此時(shí)gap = 2，依次類推增大gap就行了，什么時(shí)候結(jié)束呢，直到gap大于等于數(shù)組的長(zhǎng)度時(shí)，數(shù)組肯定是有序的。這時(shí)候在進(jìn)行歸并已經(jīng)沒(méi)有意義了。

? ? ? ? 注意：劃分子區(qū)間進(jìn)行合并的時(shí)候，有可能第二個(gè)區(qū)間的長(zhǎng)度小于第一個(gè)區(qū)間的長(zhǎng)度，或者第二個(gè)區(qū)間不存在，因此需要注意，對(duì)第二個(gè)區(qū)間的邊界進(jìn)行修正或者只有第一個(gè)子區(qū)間時(shí)，這次就不需要?dú)w并排序了。

//將兩個(gè)有序小區(qū)間合并為一個(gè)
void _MergeSortSignal(int *a, int begin1, int end1, int begin2, int end2, int *tmp)//閉區(qū)間
{int begin = begin1;//保存數(shù)組起始的位置方便拷貝tmp = (int*)malloc(sizeof(int) * (10 + 1));int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//將剩下的一個(gè)數(shù)組尾插到tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}for (int j = begin ; j <= end2; ++j){a[j] = tmp[j];}free(tmp);}
// 歸并排序非遞歸實(shí)現(xiàn)
void MergeSortNonR(int* a, int n)
{//實(shí)現(xiàn)思路：這里如果借助棧來(lái)模擬會(huì)將問(wèn)題變得復(fù)雜起來(lái)，所以可以采取循環(huán)的方式//直接歸并，第一次是相鄰的兩個(gè)數(shù)歸并，這時(shí)候gap為1，第二次gap為而就是區(qū)間[i,i+gap-1] 和區(qū)間[i+gap,i+2*gap -1]進(jìn)行插入排序，依次類推//直到gap不小于數(shù)組的長(zhǎng)度就結(jié)束int gap = 1;while (gap < n){//單趟歸并排序for (int i = 0; i < n;++i){//采用閉區(qū)間//[i,i+gap-1] 和[i+gap,i+2*gap]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//調(diào)用將兩個(gè)數(shù)組合并成一個(gè)數(shù)組的函數(shù)if (begin2 >= n){break;//說(shuō)明要排序第二組不存在，只有第一組,本次不需要再排}if (end2 >= n){//需要修正第二組的邊界end2 = n - 1;}_MergeSortSignal(a, begin1, end1, begin2, end2, NULL);}gap *= 2;}
}

?

? ? ? ? ? ? ? ? 3.4.2歸并排序應(yīng)用-外排序

? ? ? ? ? ?歸并排序和其他幾種排序不太一樣，其它幾種排序適合在內(nèi)存中進(jìn)行排序，而歸并排序不僅可以在內(nèi)存中進(jìn)行排序，當(dāng)數(shù)據(jù)很多時(shí)，多到內(nèi)存中放不下，只能存放到文件中此時(shí)其它的排序都不怎么好用，但是歸并排序卻可以對(duì)數(shù)據(jù)進(jìn)行排序并且是在文件中進(jìn)行，所以歸并排序也是外排序。

? ? ? ? 現(xiàn)在模擬一種場(chǎng)景，假設(shè)，有海量的數(shù)據(jù)，這些數(shù)據(jù)無(wú)法一次加載到內(nèi)存中，現(xiàn)在請(qǐng)你編寫一個(gè)程序?qū)@些數(shù)據(jù)進(jìn)行排序，并將結(jié)果保存在文件中。

? ? ? ? 思路是：

? ? ? ? 1.首先我們需要將這些數(shù)據(jù)劃分成很多份，并且劃分出來(lái)的每一份都可以一次性加載到內(nèi)存中并且進(jìn)行排序。

? ? ? ? 2.將劃分好的數(shù)據(jù)一次存放到子文件中，并且使用快排將這些數(shù)據(jù)變得有序。

? ? ? ? 3.此時(shí)已經(jīng)滿足歸并排序的先決條件，每個(gè)子序列都是有序的，此時(shí)我們只需要每次讀取兩個(gè)文件中的數(shù)據(jù)將它們比較并且合并到一個(gè)新的文件中，如法炮制直到最后將所有的有序子區(qū)間合并成一個(gè)文件，此時(shí)這個(gè)文件中的數(shù)據(jù)都是有序的。

????????

代碼：

//將兩個(gè)文件中的有序數(shù)據(jù)合并到一個(gè)文件中并且保持有序
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){printf("fout1打開(kāi)文件失敗\n");exit(-1);}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){printf("fout2打開(kāi)文件失敗\n");exit(-1);}FILE* fin = fopen(mfile, "w");if(fin == NULL){printf("fin打開(kāi)文件失敗\n");exit(-1);}int num1, num2;int ret1 = fscanf(fout1, "%d\n", &num1);int ret2 = fscanf(fout2, "%d\n", &num2);//在文件中讀數(shù)據(jù)進(jìn)行歸并排序while (ret1 != EOF && ret2 != EOF){if (num1 < num2){fprintf(fin, "%d\n", num1);//再去fout1所指的文件中讀取數(shù)據(jù)ret1 = fscanf(fout1, "%d\n", &num1);}else{fprintf(fin, "%d\n", num2);//再去fout2所指的文件中讀取數(shù)據(jù)ret2 = fscanf(fout2, "%d\n", &num2);}}while (ret1 != EOF){fprintf(fin, "%d\n", num1);ret1 = fscanf(fout1, "%d\n", &num1);}while (ret2 != EOF){fprintf(fin, "%d\n", num2);ret2 = fscanf(fout2, "%d\n", &num2);}fclose(fout1);fclose(fout2);fclose(fin);
}
void MergeSortFile(const char* file)//文件歸并排序
{//打開(kāi)文件FILE* fout = fopen(file, "r");if (fout == NULL){printf("打開(kāi)文件失敗\n");exit(-1);}int n = 10;int a[10] = { 0 };char subr[1024] ;/*memset(subr, 0, 1024);memset(a, 0, sizeof(int) * n);*/int num = 0;int i = 0;int fileI = 1;while (fscanf(fout, "%d\n",&num )!=EOF){if (i < n - 1){a[i++] = num;} else{a[i] = num;QuickSort(a, 0, n - 1);//對(duì)內(nèi)存中的數(shù)據(jù)進(jìn)行排序sprintf(subr, "%d", fileI++);FILE* fin = fopen(subr, "w");if (fin == NULL){printf("打開(kāi)文件失敗\n");exit(-1);}//寫數(shù)據(jù)到文件中for (int j = 0; j < n; ++j){fprintf(fin, "%d\n", a[j]);}//關(guān)閉文件i = 0;//置零對(duì)下一組數(shù)據(jù)進(jìn)行操作/*memset(subr, 0, 1024);memset(a, 0, sizeof(int) * n);*/fclose(fin);}}//外排序//利用互相歸并到文件中，實(shí)現(xiàn)整體有序char file1[100] = "1";char file2[100];char mfile[100] = "12";for (int i = 2; i <= n; ++i){sprintf(file2, "%d", i);//讀取FIle和file2，進(jìn)行歸并排序出mfile_MergeFile(file1, file2, mfile);strcpy(file1,mfile);sprintf(mfile, "%s%d", mfile, i + 1);}fclose(fout);return NULL;
}

?

? ? ? ? 3.5非比較排序?

? ? ? ? 非比較排序顧名思義就是不用對(duì)元素進(jìn)行比較就可以進(jìn)行排序了，這里介紹的是計(jì)數(shù)排序，?

計(jì)數(shù)排序又叫鴿巢原理，是對(duì)哈希直接定值法的變形應(yīng)用。操作步驟：

? ? ? ? 1.統(tǒng)計(jì)相同元素出現(xiàn)的次數(shù)

? ? ? ? 2.根據(jù)統(tǒng)計(jì)結(jié)果將序列回收到原來(lái)的序列中

?

代碼：

// 計(jì)數(shù)排序
void CountSort(int* a, int n)
{//先遍歷數(shù)組，找出最大值和最小值用來(lái)確定范圍int max = a[0];int min = a[0];for (int i = 0; i < n; ++i){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//然后根據(jù)最大值和最小值的范圍開(kāi)辟空間int range = max - min + 1;int* CountArray = (int*)calloc(sizeof(int), range);//統(tǒng)計(jì)原數(shù)組中每個(gè)數(shù)出現(xiàn)的次數(shù)for (int i = 0; i < n; ++i){CountArray[ a[i] - min ] ++ ;//利用相對(duì)位置來(lái)計(jì)算數(shù)據(jù)出現(xiàn)的個(gè)數(shù)}/*Print(CountArray, 9);printf("\n");*///將臨時(shí)數(shù)組中的數(shù)，覆蓋到原數(shù)組中int j = 0;for (int i = 0; i < range; ++i){while (CountArray[ i ]--){a[j++ ] = i + min;//將每個(gè)數(shù)據(jù)從臨時(shí)數(shù)組中拿出來(lái)加上相對(duì)數(shù)據(jù)min，然后對(duì)數(shù)組進(jìn)行覆蓋}}//釋放臨時(shí)開(kāi)辟的空間free(CountArray);
}

?

? ? ? ? 計(jì)數(shù)排序的特性總結(jié)：

??1.計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍和場(chǎng)景有限。

? 2.時(shí)間復(fù)雜度O（max(N ,范圍)）

? 3.空間復(fù)雜度O(范圍)

? ?

4.排序算法的復(fù)雜度及穩(wěn)定性的分析??

?????????

? ? ? ? 什么是穩(wěn)定性呢，通俗的來(lái)說(shuō)就是相同元素在進(jìn)過(guò)排序后它們?cè)跀?shù)組中的相對(duì)位置不變，那么穩(wěn)定或者不穩(wěn)定有什么影響呢？在一些特殊的場(chǎng)景下是有影響的，比如，在一場(chǎng)考試中，要給前三名頒獎(jiǎng)，如何確定前三名呢？比如前五名的成績(jī)分別是：99 98 97 97 97，這些的情況下，是無(wú)法直接確定前三名的，因?yàn)榈谌?#xff0c;四，五名的成績(jī)是相同的，那么這時(shí)候還有另一條規(guī)定就是這場(chǎng)比賽中成績(jī)相同時(shí)，用時(shí)短?的在前面。那么這樣的話，通過(guò)穩(wěn)定的排序就可以確定前三名且對(duì)大家都是公平的，但是如果是不穩(wěn)定的排序，這個(gè)結(jié)果是不公平的。?

? ? ? ? 選擇排序是不穩(wěn)定的，如果在一組序列中出現(xiàn)多個(gè)相同的最大值，選擇哪一個(gè)就是問(wèn)題，或者是下圖這種情況：?

? ? ? ? 堆排序也是不穩(wěn)定的，在建堆或者選數(shù)的時(shí)候要進(jìn)行向下調(diào)整，向下調(diào)整的時(shí)候可能會(huì)改變相同元素的相對(duì)順序，如圖：?

? ? ? ? ?快速排序也是不穩(wěn)定的，因?yàn)樵谶x某個(gè)基準(zhǔn)進(jìn)比較時(shí)，可能相對(duì)順序就會(huì)發(fā)生改變。????????

? ? ? ? 希爾排序也是不穩(wěn)定的，因?yàn)樵陬A(yù)排序時(shí)，相同的數(shù)可能被分到不同的組，所以它們的相對(duì)次序就沒(méi)有辦法保證了。計(jì)數(shù)排序因?yàn)槭墙y(tǒng)計(jì)原來(lái)數(shù)組中每個(gè)元素出現(xiàn)的次數(shù)，所以相同元素的相對(duì)位置是沒(méi)有辦法保證的。?