目錄

基本排序

一.冒泡排序

二.選擇排序

三.插入排序

進(jìn)階排序（遞歸實(shí)現(xiàn)）

一.快排hoare排序

1.單趟排序

快排步湊

快排的優(yōu)化

（1）三數(shù)取中

（2）小區(qū)間優(yōu)化

二.前后指針?lè)?遞歸實(shí)現(xiàn))

三.快排的非遞歸實(shí)現(xiàn)(前后指針?lè)ǖ姆沁f歸)

快排的挖坑法的實(shí)現(xiàn)

二.堆排序

1.建堆的選擇

2.堆排序的實(shí)現(xiàn)

二希爾排序

三.歸并排序(遞歸實(shí)現(xiàn)與非遞歸的實(shí)現(xiàn))

歸并排序（非遞歸實(shí)現(xiàn)）

四.非比較排序(計(jì)數(shù)排序)

計(jì)數(shù)排序的缺陷

五.排序總結(jié)

穩(wěn)定性的概念

六,排序的選擇題練習(xí)與鞏固

---

歡迎各位大佬的關(guān)顧，能給個(gè)贊就好了QWQ，由于篇幅很大，可以根據(jù)目錄跳轉(zhuǎn)你想看的排序哦！！

基本排序

一.冒泡排序

冒泡排序即，每次相鄰比較排序，每次將最小或最大固定在數(shù)組最后

void BubbleSort(int* arr, int len)
{for (int i = 0; i < len; i++){int flag = 1;for (int j = 0; j < len - i-1; j++){if (arr[j] > arr[j+1]){flag = 0;Swap(&arr[j + 1],&arr[j]);}}if (flag)break;}
}

二.選擇排序

很明顯選擇排序就是去找最小或者最大的下標(biāo)然后賦值給原始位置,代碼實(shí)現(xiàn)如下

void SelectSort(int* arr, int len)
{for (int i = 0; i < len-1; i++){int min = i;for (int j = i + 1; j < len; j++){if (arr[j] < arr[min])min = j;}Swap(&arr[min], &arr[i]);}
}

但是這種選擇排序也太low了讓我們來(lái)實(shí)現(xiàn)一個(gè)Plus版本，一次循環(huán)找到最大與最小

int SelectSortPlus(int* arr, int len)
{int begin = 0;int end = len - 1;for (int i = begin; i <=end-1; i++){int min = begin;int max = begin;for (int j = i+1; j <= end; j++){if (arr[j] < arr[min])min = j;if (arr[j] > arr[max])max = j;}Swap(&arr[begin], &arr[min]);if (begin == max)//注意這里當(dāng)begin與max的下標(biāo)一樣的時(shí)候，會(huì)被先換導(dǎo)致bugmax = min;Swap(&arr[end], &arr[max]);begin++;end--;}
}

三.插入排序

看動(dòng)圖可以很容易的理解插入排序就是將已排好的序的后一個(gè)與前面的進(jìn)行比較，比它大或小的往后移動(dòng)

void InsertSort(int* a, int len)
{for (int i = 0; i < len - 1; i++){int end = i;int temp = a[end + 1];while (end >= 0){if (temp < a[end]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = temp;}}
}

進(jìn)階排序（遞歸實(shí)現(xiàn)）

一.快排hoare排序

快排有著多種實(shí)現(xiàn)方式我們下面這個(gè)是hoare（創(chuàng)始人）的排序方式

快速排序是一種高效的排序現(xiàn)在來(lái)讓我們來(lái)實(shí)現(xiàn)一下

1.單趟排序

想要寫出一個(gè)排序首先我們要去理解這個(gè)排序的單趟 單趟如圖所示

如圖我們可以發(fā)現(xiàn)它的步驟如下

快排步湊

(1)選出基準(zhǔn)值key 為 left

（2）右邊r先走找到比key小的停止

(3)右邊r找到的情況下,左邊L再開始找比key大的值

（3）左邊L找到的情況下停止，將這兩個(gè)值進(jìn)行交換

循環(huán)上面的操作

直到他們相遇，將相遇的位置的值與key值交換

這就是快排的單趟排序，接下來(lái)讓我們來(lái)實(shí)現(xiàn)一下

void QuickSort2(int* arr, int left, int right)
{int key = left;int begin = left;int end = right;while (begin < end){//先從右邊開始找小 //注意結(jié)束條件 begin一定<endwhile (begin < end && arr[end] >= arr[key]){--end;}//再?gòu)淖筮呎掖體hile (begin < end && arr[begin] <= arr[key]){++begin;}//兩邊都找到了之后進(jìn)行交換Swap(&arr[begin], &arr[end]);}//最后相遇再與key交換Swap(&arr[begin], &arr[key]);}
}

想必這里大家會(huì)有一些疑問(wèn)，為什么

1.為什么要右邊先走，左邊先走可以嗎

2.為什么最后交換key的位置就固定了

3.要怎么樣才能實(shí)現(xiàn)排序的效果

循環(huán)的實(shí)現(xiàn)，既然單趟可以固定住key值在整個(gè)數(shù)里面的想要排序的位置，那我們可不可以將這個(gè)數(shù)組進(jìn)行分割[left~key-1]key[key+1~right]

運(yùn)用遞歸來(lái)實(shí)現(xiàn)呢

答案是肯定的

只需要每次遞歸進(jìn)行分割，固定n的值的位置，如下圖所示

如圖所示很明顯當(dāng)我們進(jìn)行遞歸的時(shí)候每次的位置都將被固定,從而實(shí)現(xiàn)了排序

代碼如下

void QuickSort2(int* arr, int left, int right)
{//返回條件if (left >= right)return;int key = left;int begin = left;int end = right;while (begin < end){//先從右邊開始找小 //注意結(jié)束條件 begin一定<endwhile (begin < end && arr[end] >= arr[key]){--end;}//再?gòu)淖筮呎掖體hile (begin < end && arr[begin] <= arr[key]){++begin;}//兩邊都找到了之后進(jìn)行交換Swap(&arr[begin], &arr[end]);}//最后相遇再與key交換Swap(&arr[begin], &arr[key]);//遞歸排序分割成兩份//[left~key-1] key [key+1~right]最后相遇的指針也是一樣的QuickSort2(arr, left, end - 1);QuickSort2(arr, end + 1, right);
}

到這里我們也就完成了閹割版的快排，但是距離真正的快排還是有些距離

現(xiàn)在的這個(gè)排序有著致命的缺陷如果說(shuō)在數(shù)組已經(jīng)是有些的情況下，快排的將會(huì)退化，就像是二叉樹退化為單叉樹一樣，如果我們這時(shí)還去遞歸那就會(huì)有爆棧（棧溢出）的風(fēng)險(xiǎn)，原因很簡(jiǎn)單

如下圖所示

如果是有序的情況下，那么遞歸的深度將會(huì)變成n如果數(shù)據(jù)量太大將會(huì)爆棧

所以接下來(lái)要去實(shí)現(xiàn)一下三數(shù)取中，小區(qū)間優(yōu)化來(lái)對(duì)遞歸快排進(jìn)行優(yōu)化

快排的優(yōu)化

（1）三數(shù)取中

選擇key值進(jìn)行,key值的選擇就是為了避免這種有序情況的出現(xiàn)，因?yàn)檫xkey固定key的位值，我們只需要找到中間的那個(gè)數(shù)進(jìn)行固定區(qū)間遞歸的高度將會(huì)變?yōu)?img referrerpolicy="no-referrer" alt="\log n" class="mathcode" src="https://latex.csdn.net/eq?%5Clog%20n" />解決了爆棧的風(fēng)險(xiǎn)

int GetMid2(int* arr, int left, int right)
{//三個(gè)數(shù)進(jìn)行比較 分類討論int mid = (left + right) / 2;if (arr[left] < arr[mid]){if (arr[mid] < arr[right]){return mid;}//arr[mid]>arr[right]else if (arr[right] < arr[left]){return left;}else{return right;}}else//arr[left]> arr[mid]{if (arr[mid] > arr[right]){return mid;}//arr[righ]>arr[mid]else if (arr[right]>arr[left]){return left;}else{return right;}}
}

（2）小區(qū)間優(yōu)化

什么是小區(qū)間優(yōu)化？在我們進(jìn)行快排的時(shí)候，如果每次的區(qū)間都能二分的化，這個(gè)遞歸的過(guò)程是可以看出一顆二叉樹，而在滿二叉樹的葉子節(jié)點(diǎn)個(gè)數(shù)為整棵樹的一半，對(duì)于快排來(lái)說(shuō)它的最后一層和倒數(shù)第二層，是不用去排和只排一個(gè)數(shù)的，但是卻還要開辟棧幀，所以我們這里使用小區(qū)間優(yōu)化帶代碼如下直接使用當(dāng)區(qū)間小于10時(shí)進(jìn)行插入排序

//小區(qū)間優(yōu)化 提升效率節(jié)省空間
if ((right - left + 1) < 10)//減少遞歸次數(shù)
{//加上偏移量leftInsertSort(arr+left, right - left + 1);
}
else
{//進(jìn)行遞歸
}

注意事項(xiàng)

二.前后指針?lè)?遞歸實(shí)現(xiàn))

由于hoare版本的有些復(fù)雜要去考慮什么右邊先走之類的，所以又有人想出了更加簡(jiǎn)單跟容易理解的辦法，前后指針?lè)?#xff0c;過(guò)程如圖所示

可以發(fā)現(xiàn)與hoare版本大體一致都是去選擇key與key比較,不同點(diǎn)在于,只有是cur去找比key小的值，當(dāng)找到比key小的值的時(shí)候++prev然后與cur位置的值進(jìn)行交換，最后當(dāng)cur走到最后，prev的值再與key位置的值進(jìn)行交換，比起hoare版本簡(jiǎn)單了許多，接下來(lái)我們來(lái)嘗試實(shí)現(xiàn)一下

void QuickSortByPointer(int* arr, int left, int right)
{if (left >= right)return;//三數(shù)取中int mid = GitMid(arr,left,right);Swap(&arr[mid], &arr[left]);int key = left;int prev = left;int cur = prev+1;//三數(shù)取中if ((right - left + 1) < 10){InsertSort(arr+left, right - left + 1);//加上left}else{while (cur <= right){if (arr[key] > arr[cur]&&++prev != cur)//為什么要寫成這樣？Swap(&arr[prev], &arr[cur]);cur++;}Swap(&arr[prev], &arr[key]);//區(qū)間變?yōu)閇0,prev-1]prev[prev+1,right]QuickSortByPointer(arr, left, prev - 1);//值給錯(cuò)了應(yīng)該是leftQuickSortByPointer(arr, prev + 1, right);}
}

你以為到這里快排就結(jié)束了嘛其實(shí)還是馬達(dá)馬達(dá)得是(遠(yuǎn)遠(yuǎn)沒有結(jié)束),雖然我們加上三數(shù)取中，與小區(qū)間的優(yōu)化但是如果數(shù)據(jù)量過(guò)大還是會(huì)有爆棧的風(fēng)險(xiǎn)（棧的空間比較小），所以我們可以使用數(shù)據(jù)結(jié)構(gòu)的棧來(lái)模擬實(shí)現(xiàn)程序中的壓棧與出棧，（由于是在堆中建立，內(nèi)存巨大,8G的內(nèi)存不可能溢出把！）

三.快排的非遞歸實(shí)現(xiàn)(前后指針?lè)ǖ姆沁f歸)

可以看見我們先是將每次的單次排序進(jìn)行封裝的

我們可以想象一下在程序中棧幀的建立與銷毀的過(guò)程，然后我們也可以自己使用數(shù)據(jù)結(jié)構(gòu)的棧來(lái)實(shí)現(xiàn)

快排其實(shí)是可以看作二叉樹的前序遍歷的，但是棧又是后進(jìn)先出，想要先得到左邊界的值就需要先進(jìn)右邊，想要得到右邊界的值就需要先進(jìn)左邊

void QuickSortNoR(int* arr, int begin, int end)
{Stack st;CreatStack(&st);StackPush(&st, end);StackPush(&st, begin);while (StackGetSize(&st)!=0){int left = StackPop(&st);//我的Pop是即出又返回棧頂元素的因?yàn)楹筮M(jìn)先出想要先得到left進(jìn)右int right = StackPop(&st);//小區(qū)間優(yōu)化if ((right - left + 1) / 2 < 10)InsertSort(arr + left, right - left + 1);else{//開始模擬遞歸int key = PartPointer(arr, left, right);//這個(gè)函數(shù)是每一次的單趟排序if (key + 1 < right)//進(jìn)行遞歸由于后進(jìn)先出 先進(jìn)右區(qū)間{StackPush(&st, right);//后進(jìn)先出由于我們的右區(qū)間是后出 所以先進(jìn)StackPush(&st, key + 1);}if (left < key - 1)//注意錯(cuò)誤之處區(qū)間不要寫錯(cuò)了{(lán)StackPush(&st, key - 1);StackPush(&st, left);}}}
}
int PartPointer(int* arr, int left, int right)
{//三數(shù)取中int mid = GitMid(arr, left, right);Swap(&arr[mid], &arr[left]);int key = left;int prev = left;int cur = prev + 1;while (cur <= right){if (arr[key] > arr[cur])Swap(&arr[++prev], &arr[cur]);cur++;}Swap(&arr[prev], &arr[key]);return prev;//返回key的位置 prev就是key中間值 然后進(jìn)行區(qū)間的分割同上
}

快排的挖坑法的實(shí)現(xiàn)

（由于篇幅有限這里不在過(guò)多講解）

int PartSort2(int* a, int begin, int end)
{//begin是坑int key = a[begin];while (begin < end){while (begin < end && a[end] >= key)--end;// end給begin這個(gè)坑，end就變成了新的坑。a[begin] = a[end];while (begin < end && a[begin] <= key)++begin;// end給begin這個(gè)坑，begin就變成了新的坑。a[end] = a[begin];}a[begin] = key;return begin;
}

二.堆排序

學(xué)習(xí)完了快排，接下來(lái)學(xué)習(xí)堆，首先我們要知道堆的概念，

堆在邏輯結(jié)構(gòu)上是一個(gè)完全二叉樹，在物理結(jié)構(gòu)上是一個(gè)數(shù)組，

想要找到兒子節(jié)點(diǎn)就是(parent-1)/2

想要找到父親節(jié)點(diǎn)就是child*2+1

如果想要深入理解堆可以看我的這一篇博客堆的實(shí)現(xiàn)與堆排序（純C語(yǔ)言版）-CSDN博客

1.建堆的選擇

當(dāng)我們想要進(jìn)行排序的時(shí)候首先要模擬堆的插入過(guò)程進(jìn)行建堆，這里有個(gè)問(wèn)題如果想要降序排列那么應(yīng)該建小堆還是大堆呢，在我剛開學(xué)學(xué)習(xí)的時(shí)候想的是肯定是建大堆啊因?yàn)檫@樣根節(jié)點(diǎn)就是最大的然后再出堆,其實(shí)這樣想就錯(cuò)了，這樣只是出堆降序，不是數(shù)組本身進(jìn)行了降序排列，所以降序是其實(shí)是建小堆，升序其實(shí)是建大堆.那又是怎么實(shí)現(xiàn)的呢

2.堆排序的實(shí)現(xiàn)

在進(jìn)行建堆之后（小堆降序來(lái)舉例），我們就只需要模擬出堆，這時(shí)每次最小的數(shù)就被放在了最后的位置,最后完成排序后，整個(gè)數(shù)據(jù)就有序,如圖當(dāng)我們想要升序排列的時(shí)候建大堆

下面是完整的代碼

void HeapSort(int* a, int max)//max為最大個(gè)數(shù)
{//建隊(duì)for (int i = 0; i <max; i++){AdjustUp(a, i);//模擬插入建小堆}//排序int end = max - 1;//找到最后一個(gè)元素的下標(biāo)進(jìn)行交換while (end>0){Swap(&a[0], &a[end]);AdjustDown(a, 0, end);--end;//最后的有序不在排序}
}

其實(shí)第一步建堆算法還沒有做到極致,還可以倒著向下調(diào)整,這樣的時(shí)間復(fù)雜度更低

//建堆法2
for (int i = (max - 1 - 1) / 2; i >= 0; i--)//找到第一個(gè)非葉子結(jié)點(diǎn) 倒著進(jìn)行想下調(diào)整
{AdjustDown(a, i, max-1);
}

二希爾排序

希爾排序是一個(gè)時(shí)間復(fù)雜度大約為的排序算法，

它其實(shí)就是運(yùn)用的插入排序

它的排序可以分為2步

1.預(yù)排序分為gap組進(jìn)行

2.當(dāng)gap=1時(shí)即為選擇排序

希爾排序的實(shí)質(zhì)就是如果在排一個(gè)升序的數(shù)組，如果大的在很前面，每次就是一步一步的移動(dòng)，而當(dāng)有了gap之后，移動(dòng)的步長(zhǎng)將會(huì)變大，大的數(shù)將會(huì)以更快的速度移到后面

我們將插入排序來(lái)進(jìn)行一下比較

void InsertSort(int* a, int len)
{for (int i = 0; i < len - 1; i++){int end = i;int temp = a[end + 1];while (end >= 0){if (temp < a[end]){a[end + 1] = a[end];end--;}else{break;}a[end + 1] = temp;}}
}

可以看見在進(jìn)行插入排序的時(shí)候，此時(shí)的步長(zhǎng)gap為1，每次只會(huì)往后面進(jìn)行一步，所以我們這里只需去改變想要排序的步長(zhǎng)即可

下面是代碼的實(shí)現(xiàn)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保證最后一個(gè)gap一定是1// gap > 1時(shí)是預(yù)排序// gap == 1時(shí)是插入排序gap = gap / 3 + 1;for (size_t 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;}}
}

我們可以發(fā)現(xiàn)，我們上面是一組一組來(lái)排序

也可以多組并走都是一樣的

三.歸并排序(遞歸實(shí)現(xiàn)與非遞歸的實(shí)現(xiàn))

歸并排序的思想就是分治法(分而治之),如圖所示

首先我們要?jiǎng)?chuàng)建一個(gè)臨時(shí)的數(shù)組

運(yùn)用了二叉樹的后序遍歷的思維，先將數(shù)組拆分，拆分后的數(shù)組又來(lái)進(jìn)行合并，在進(jìn)行合并的兩個(gè)數(shù)組分別有序，只需要比較一次將小的放入到臨時(shí)的數(shù)組當(dāng)中，放完成后再拷貝回去完成排序

重點(diǎn)就是在進(jìn)行合并的時(shí)候兩個(gè)數(shù)組是有序的！

讓我們來(lái)實(shí)現(xiàn)一下

l

000lkklkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkklkkkkkkkkkkkkkkkkkkkkkkkk? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 222

代碼如下

void MergeSort(int* arr, int len)
{int* temp = (int*)malloc(sizeof(int) * len);_MergeSort(arr,temp,0,len-1);free(temp);temp = NULL;
}
void _MergeSort(int* arr, int* temp, int left, int right)
{//返回條件if (left >= right)return;//進(jìn)行遞歸//分成[left mid][mid+1,right]不能寫成[left mid-1][mid,right]分區(qū)間的時(shí)候?qū)?huì)出現(xiàn)問(wèn)題//單趟排序 將左右區(qū)間看作有序數(shù)組 進(jìn)行比較放入temp數(shù)組中int mid = (left + right) / 2;//[left mid][mid+1,right]int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;_MergeSort(arr, temp, begin1, end1);//左區(qū)間_MergeSort(arr, temp, begin2, end2);//右區(qū)間int i = 0;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){temp[i++] = arr[begin1++];}else//直接else{temp[i++] = arr[begin2++];}}//循環(huán)結(jié)束后還有元素全部放后面while (begin1 <= end1){temp[i++] = arr[begin1++];}//循環(huán)結(jié)束后還有元素全部放后面while (begin2 <= end2){temp[i++] = arr[begin2++];}//進(jìn)行拷貝回去memcpy(arr+left, temp, i*sizeof(int));
}

歸并排序（非遞歸實(shí)現(xiàn)）

想要實(shí)現(xiàn)歸并的非遞歸，我們是否還需要像快排一樣去模擬棧呢，當(dāng)我們?nèi)∧M棧的時(shí)候由于歸并的遞歸是一個(gè)后序遍歷，而棧無(wú)法去記錄值，所以使用棧就要用兩個(gè)，較為麻煩，使用我們直接用下面這種思想

由上面遞歸實(shí)現(xiàn)的歸并排序很容易想，其中的gap為每個(gè)小組的個(gè)數(shù)

但是好像還有一個(gè)問(wèn)題，數(shù)組越界的問(wèn)題

當(dāng)我們使用了上面的數(shù)據(jù)進(jìn)行分組的時(shí)候，所以我們要進(jìn)行區(qū)間的判斷

加入

if (begin2 > len - 1)//begin2已經(jīng)越界,說(shuō)明只有一組了沒必要再排
{break;
}
if (end2 > len - 1)//end2越界了進(jìn)行修正即可
{end2 = len - 1;
}

完整的代碼如下

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}// gap每組歸并數(shù)據(jù)的數(shù)據(jù)個(gè)數(shù)int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){// [begin1, end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);// 第二組都越界不存在，這一組就不需要?dú)w并if (begin2 >= n)break;// 第二的組begin2沒越界，end2越界了，需要修正一下，繼續(xù)歸并if (end2 >= n)end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2])//注意等號(hào)這樣才會(huì)穩(wěn)定{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));}//memcpy(a , tmp , sizeof(int) *n );//printf("\n");gap *= 2;}free(tmp);tmp = NULL;
}

四.非比較排序(計(jì)數(shù)排序)

接下來(lái)讓我們來(lái)學(xué)習(xí)最后一個(gè)排序，這個(gè)排序的特點(diǎn)是非比較的排序，通過(guò)建立一個(gè)數(shù)組來(lái)存放數(shù)組中每個(gè)數(shù)出現(xiàn)的次數(shù)，來(lái)實(shí)現(xiàn)排序

首先來(lái)思考我們想要開辟的數(shù)組的大小，那是否就是原數(shù)組的長(zhǎng)度大小呢，因?yàn)橐鎯?chǔ)每個(gè)元素出現(xiàn)的次數(shù)，那么我們開辟數(shù)組必須是連續(xù)的，在開辟數(shù)組長(zhǎng)度大小的時(shí)候有個(gè)細(xì)節(jié)，如果每次都從0開始建立計(jì)數(shù)數(shù)組，那如果遇到一個(gè)最小值為99，最大值為110的數(shù)組，那我們還是需要從0開始建立數(shù)組，前面明明一個(gè)數(shù)都沒有出現(xiàn)但是我們卻還是去開辟的數(shù)組，浪費(fèi)了很多的空間，所以我們只需要去找到最大與最小的那個(gè)值，計(jì)算出rang=最大值-最小值+1（注意要加一），所以計(jì)數(shù)數(shù)數(shù)組的大小為rang，那我們?cè)谶M(jìn)行計(jì)數(shù)的時(shí)候就只需要進(jìn)行-min就可以了

然后是進(jìn)行排序，當(dāng)計(jì)數(shù)數(shù)組里不為0說(shuō)明當(dāng)前位置有映射值進(jìn)行自減1.加上min賦值給原數(shù)組實(shí)現(xiàn)排序效果

代碼如下

void CountSort2(int* arr, int len)
{//找到原數(shù)組的最大與最小值int min = arr[0];int max = arr[len - 1];for (int i = 0; i < len; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}int rang = max - min + 1;//開辟計(jì)數(shù)數(shù)組 注意這里要初始化開辟的計(jì)數(shù)數(shù)組 這樣奇計(jì)數(shù)數(shù)組才全是0int* count = (int*)calloc(rang,sizeof(int) * rang);//進(jìn)行計(jì)數(shù)for (int i = 0; i < len; i++){count[arr[i] - min]++;}//進(jìn)行排序int j = 0;for (int i = 0; i < rang; i++){while (count[i]--)//當(dāng)count[i]的元素不為0的時(shí)候說(shuō)明當(dāng)前映射有值{arr[j++] = i + min;}}}

計(jì)數(shù)排序的缺陷

既然計(jì)數(shù)排序是一種映射的方法，所以是只能對(duì)整數(shù)進(jìn)行排列的

五.排序總結(jié)

學(xué)習(xí)完了上面的排序現(xiàn)在我們來(lái)進(jìn)行一下總結(jié)，

排序? ? ? ? ?平局時(shí)間復(fù)雜度? ? 最壞時(shí)間復(fù)雜度 最好時(shí)間復(fù)雜度 穩(wěn)定性

冒泡排序? ? ? ? ? ? ? ? O()? ????????????????O()? ? ? ?O()? ? ? ?? ? ? ? ?穩(wěn)定?

選擇排序????????????????O()?????????????????O()????????O()?? ? ? ? ? ? ? 不穩(wěn)定

插入排序? ? ? ? ? ? ? ? O()?????????????????O()????????O()? ? ? ? ? ? ? ??穩(wěn)定

希爾排序? ? ? ? ? ? ? ? O()? ? ? ? ? ? ??O()????????O()? ? ? ? ? ? ?不穩(wěn)定

堆排序? ? ? ? ? ? ? ? ? ? O()??O()O() 不穩(wěn)定

快速排序????????????????O()? ?O()?????????O()? ? ? ?不穩(wěn)定

歸并排序?????????????????O()? ??O()???O() 穩(wěn)定

?

穩(wěn)定性的概念

上表的穩(wěn)定性是什么意思？其實(shí)就是相同數(shù)據(jù)的前后位置是否發(fā)生改變，如下面紅色5與藍(lán)色5當(dāng)排序完成后紅色5還在藍(lán)色5前面就是穩(wěn)定的

六,排序的選擇題練習(xí)與鞏固

學(xué)完上面的知識(shí)，不來(lái)兩道題檢測(cè)一下是不知道自己真正掌握了沒有的下面讓我們來(lái)做幾道題加深一下印象。

1.用某種排序方法對(duì)關(guān)鍵字序列 25 84 21 47 15 27 68 35 20 進(jìn)行排序，序列的變化情況采樣如下：

20 15 21 25 47 27 68 35 84

15 20 21 25 35 27 47 68 84

15 20 21 25 27 35 47 68 84

請(qǐng)問(wèn)采用的是以下哪種排序算法（ ）

A.選擇排序

B.希爾排序

C.歸并排序

D.快速排序

答案：D

解析：

此題中的排序是快排二分排序的思想，第一趟的基準(zhǔn)值是25，第二趟的基準(zhǔn)值分別是20，47，第三趟的基準(zhǔn)值分別是15，21，35，68

?

2.下面的排序算法中，初始數(shù)據(jù)集的排列順序?qū)λ惴ǖ男阅軣o(wú)影響的有（ ）

① 快速排序

② 希爾排序

③ 插入排序

④ 堆排序

⑤ 歸并排序

⑥ 選擇排序

A.①④⑤

B.④⑤⑥

C.②③⑥

D.②③⑤⑥

答案：B

解析：

快排： 初始順序影響較大，有序是，性能最差

插入: 接近有序，性能最好

希爾：希爾是對(duì)插入排序的優(yōu)化，這種優(yōu)化是在無(wú)序的序列中才有明顯的效果，如果序列接近有序，反而是插入最優(yōu)。

堆排，歸并，選擇對(duì)初始順序不敏感

3.下列排序方法中，每一趟排序結(jié)束時(shí)都至少能夠確定一個(gè)元素最終位置的方法是（ ）

① 選擇排序

② 歸并排序

③ 快速排序

④ 堆排序

A.①④

B.①②④

C.①③④

D.①②③④

?

答案：C

解析：

選擇排序每次選一個(gè)最值，放在最終的位置

快速排序每次基準(zhǔn)值的位置也可以確定

堆排序每次堆頂元素的位置也可以確定

所以這三種方法都可以每次至少確定一個(gè)元素的位置

而歸并排序每次都需要對(duì)n個(gè)元素重新確定位置，所以不能保證每次都能確定一個(gè)元素位置，有可能每次排序所有元素的位置都為發(fā)生變化。

?

4.現(xiàn)有數(shù)字序列 5 11 7 2 3 17，目前要通過(guò)堆排序進(jìn)行降序排序，那么由該序列建立的初始堆應(yīng)為（ ）

A.2 3 7 11 5 17

B.17 11 7 2 3 5

C.17 11 7 5 3 2

D.2 3 5 7 11 17

答案：A

解析：

要降序排列，所以要建小堆，每次把堆頂元素放在當(dāng)前堆的最后一個(gè)位置

建堆要進(jìn)行向下調(diào)整算法（從最后一個(gè)非葉子節(jié)點(diǎn)開始進(jìn)行向下調(diào)整算法，直到根元素）

5

11 7

2 3 17

5

2 7

11 3 17

2

3 7

11 5 17

所以初始堆序列為： 2 3 7 11 5 17

5.下列選項(xiàng)中，不可能是快速排序第2趟排序后的結(jié)果的是（ ）

A.2 3 5 4 6 7 9

B.2 7 5 6 4 3 9

C.3 2 5 4 7 6 9

D.4 2 3 5 7 6 9

?

答案：C

解析：

這里說(shuō)的是快排的第二趟，即在第一趟快排的結(jié)果的基礎(chǔ)上進(jìn)行的，如果已經(jīng)經(jīng)過(guò)了一趟排序，則會(huì)通過(guò)第一趟選擇的基準(zhǔn)值劃分兩個(gè)子區(qū)間，每個(gè)子區(qū)間也會(huì)以區(qū)間內(nèi)選擇的基準(zhǔn)值劃分成兩部分。

A: 第一趟的基準(zhǔn)值可以為2， 第二趟的基準(zhǔn)值可以為3

B: 第一趟的基準(zhǔn)值可以為2， 第二趟的基準(zhǔn)值可以為9

C: 第一趟的基準(zhǔn)值只能是9，但是第二趟的基準(zhǔn)值就找不出來(lái)，沒有符合要求的值作為基準(zhǔn)值，所以不可能是一個(gè)中間結(jié)果。

D: 第一趟的基準(zhǔn)值可以為9， 第二趟的基準(zhǔn)值可以為5

由于個(gè)人精力有限，如有錯(cuò)誤歡迎指出！！！

小bit！！！