文章目錄
- 直接插入排序
- 代碼實作
- 復雜度的計算
- 希爾排序
- 希爾排序的預排序
- 代碼實作
- 選擇排序
- 代碼實作
- 堆排序
- 冒泡排序
- 代碼實作
- 快速排序
- 遞回實作
- Hoare版本
- 代碼實作
- 遞回圖解
- 挖坑法
- 代碼實作
- 遞回圖解
- 前后指標法
- 代碼實作
- 遞回圖解
- 非遞回實作
- Hoare版本
- 挖坑法
- 前后指標法
- 非遞回快排代碼實作
- 圖解代碼
- 快速排序的兩個優化
- 1.三數取中
- 代碼實作
- 2.小區間的優化
- 代碼實作
- 歸并排序
- 遞回實作
- 遞回圖解
- 區間劃分要注意（死遞回）
- 非遞回實作
- 代碼實作
- 遞回圖解
- 計數排序
- 絕對映射和相對映射
- 代碼實作
- 八大排序性能測驗
💢 注：以下排序都是以排升序為例，
直接插入排序
直接插入排序的主要思路就是：
1.首先默認第一個元素是有序的，
2.然后將其下一個元素作為待排序的元素，插入到前面有序序列的相應位置，至于插入的程序，如果遇到比待排序大的元素，則這個元素后移，直到遇到比其小的元素，然后將待插入元素放入其前一個位置，
代碼實作
void Insertsort(int *a, int sz)
{
int i = 0;
for (i = 0; i < sz-1; i++)
{
//用j來記錄i的位置，這樣可以省得到時候有些情況i從頭或接近從頭開始走
int j = i;
int temp = a[i + 1];
while (i >= 0)
{
if (temp<a[i])
{
a[i + 1] = a[i];
i--;
}
else
{
break;
}
}
a[i + 1] = temp;
i = j;
}
}
注：絕大部分的直接插入排序演算法其實是沒有在代碼中記錄i的位置的，其實記錄了i的位置可以提高執行效率，因為這樣可以省得到時候有些情況i從頭或接近從頭開始走，
復雜度的計算
在代碼中，創建的臨時變數個數是常數個，所以空間復雜度為O（1），
希爾排序
在上面的直接插入排序中我們會發現：
1.普通插入排序的時間復雜度最壞情況下為O(N2)，此時待排序列為逆序，或者說接近逆序，
2.普通插入排序的時間復雜度最好情況下為O(N)，此時待排序列為升序，或者說接近升序，
于是希爾這個科學家就想：若是能先將待排序列進行一次預排序，使待排序列接近有序（接近我們想要的順序），然后再對該序列進行一次直接插入排序，因為此時直接插入排序的時間復雜度為O(N)，那么只要控制預排序階段的時間復雜度不超過O(N^2)，那么整體的時間復雜度就比直接插入排序的時間復雜度低了，
希爾排序的預排序
希爾排序，又稱縮小增量法，那么如何縮小增量了？
1.先選定一個小于N的整數gap作為第一增量，然后將所有距離為gap的元素分在同一組，并對每一組的元素進行直接插入排序，然后再取一個比第一增量小的整數作為第二增量，重復上述操作 （一般情況下我們取得第一增量大小是序列長度的一半）
2.當增量的大小減到1時，其實此時預排序已經完成了，這時已經達到我們一開始要的目的：讓序列接近我們要的順序，
3.最后對整個序列進行直接插入排序即可，
舉個例子來看下，
在這個序列中，gap=3時其實就是對原序列進行了預排序，使其接近我們要的升序，方便之后的直接排序，
注：希爾排序和直接插入排序是穩定排序：我們可以發現，在希爾排序的程序中，序列中兩個9的相對位置沒有發生改變，具有這樣特性的排序，我們稱之為穩定排序，
代碼實作
void Shellsort(int *a, int sz)
{
int i = 0;
int gap = sz / 2;
while (gap >= 1)
{
for (i = 0; i < sz-gap; i++)
{
int j = i;
int end = i;
int temp = a[i + gap]; //這兒一定要記錄下那個位置的資料，而不是寫成temp=i+gap記錄下標的形式，因為之后那個記錄的下標的位置的資料可能被前面的資料前移占據了，
while (end >= 0)
{
if (temp < a[end])
{
//a[temp] = a[end]; 因為下面要用到a[end+gap]=a[temp],所以這兒不能寫成a[temp]
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = temp;
i = j;
}
gap = gap / 2;
}
}
選取這種增量方法的時間復雜度：O（nlogn），具體這個我是這么理解的，首先預排序階段，你每次都將gap除以2，其實也就是高度次：logn，預處理中的交換次數可以看成常量，然后預處理完，這時已經接近最好情況的直接排序了，時間復雜度為O（n），所以最終的時間復雜度為O（nlogn），具體的證明程序等后序會補充更新，
空間復雜度：這里我們只定義了常數個常量，故空間復雜度為O（1），
選擇排序
選擇排序
1.首先從整個陣列中選出最小值，記錄下最小值位置的下標與第一個位置交換，這樣相當于最小值就到了頭上，
2.此時將除最小值之后的元素再來選出次小的數，與第二個位置交換，之后迭代這個程序，最終就可以排成升序，
代碼實作
void chosesort(int *a, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
int min = i;
for (int j = i; j < sz; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
swap(&a[i], &a[min]);
}
}
時間復雜度：最壞的情況下是一個等引數列為O（n^2)
空間復雜度：創建了常數個變數，為O（1）
實際上，我們可以一趟選出兩個值，一個最大值一個最小值，然后將其放在序列開頭和末尾，這樣可以使選擇排序的效率快一倍，
void chosesort(int* a, int sz)
{
int start = 0;
int end = sz - 1;
while (start < end)
{
int min = start;
int max = start;
for (int j=start; j <= end; j++)
{
if (a[j] < a[min])
{
min = j;
}
if (a[j]>a[max])
{
max = j;
}
}
swap(&a[start], &a[min]);
//萬一最大的值在最左邊，這樣max的位置的值就被最小值覆寫了，如果沒有這個處理，會導致下面交換時出錯，
if (max == start)
{
max = min;
}
swap(&a[end], &a[max]);
start++;
end--;
}
}
注：這里要小心一種極端情況：萬一最大的值在最左邊，這樣max的位置的值就被最小值覆寫了，如果沒有if這個處理，會導致下面交換時出錯，
堆排序
博主之前專門寫了一篇關于堆排序以及堆的文章，由于是最近不久寫的，這里就不再贅述了，💢堆排序以及堆相關的知識
冒泡排序
相信冒泡排序是很多小伙伴第一個知道的排序演算法，
其實它的思想正和他的取名一樣，它就是每趟排序冒出一個最大（最小）值，那么它是如何冒的了？很簡單，相鄰兩個元素比較，前一個比后一個大，則交換，
代碼實作
void Bubblesort(int *a, int sz)
{
int i = 0;
int flag = 0; //記錄原序列是否有序
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)
{
if (a[j]>a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = 1; //交換過了，說明原序列無序
}
}
if (flag == 0) //原序列一次交換都沒有發生，說明原序列本來就有序，無需在繼續進行
{
break;
}
}
}
注：這里可以自己定義一個識別符號flag來記錄原序列是否發生過交換，如果沒有發生過，則說明原序列本來就有序，無需再進行之后的趟數，
快速排序
快速排序是公認的排序之王，
其基本思想為： 任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序列分為兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右序列重復該程序，直到所有元素都排列在相應位置上為止，
對于如何按斬訓準值將待排序列分為兩子序列，常見的方式有：
1、Hoare版本
2、挖坑法
3、前后指標法
這三種方法并沒有明顯的優缺點，時間復雜度都為O（nlogn）
遞回實作
Hoare版本
Hoare版本單趟排序的基本步驟如下：
1.選一個key作為比較值，一般是最左邊或者最右邊，
2.定義一個left和right，如果key選取的是左邊就讓右邊的先走，直到right找到一個比key小的值，然后讓left從左邊走，直到讓它找到一個比key大的值，然后交換兩者，之后繼續讓right先走，left后走，直到left與right相遇停下來，
3.最終再讓相遇處與key處位置對應的值做交換，這樣就可以達到我們想要的效果了，
4.之后遞回它的左序列和右序列，最終排成升序，
注意：可能有小伙伴會問了，如果你最后key與meet（相遇處）處對應的值交換，萬一meet比key處的值大，那不就達不到我們要的效果了嗎？其實這里并不會出現這個問題，因為這種方法讓right先走了，所以不會出現這種問題，大家可以多去嘗試幾組資料看看，是不是會有這個特點
代碼實作
//快速排序（Hoare版本）
void QuickSort1(int* a, int left, int right)
{
if (left >= right)//當只有一個資料或是序列不存在時，不需要進行操作
return;
int begin = left;//L
int end = right;//R
int key = left;//key的下標
while (left < right)
{
//right先走，找小
while (left < right&&a[right] >= a[key])
{
right--;
}
//left后走，找大
while (left < right&&a[left] <= a[key])
{
left++;
}
if (left < right)
{
swap(&a[left], &a[right]);
}
}
int meet = left;//L和R的相遇點
swap(&a[key], &a[meet]);//交換key和相遇點的值
QuickSort1(a, begin, meet - 1);//key的左序列進行此操作
QuickSort1(a, meet + 1, end);//key的右序列進行此操作
}
注意：
1.這里要保存一下left和right的值，因為你在代碼程序中left和right的值會發生變化，如果你不保存，在遞回時傳參直接傳left和right的話，那時就不是我們想要的值了，
2.這里你key要記錄left的下標，而不是記錄a[left]這個數值，因為如果這樣的話，你在下面交換key位置和meet位置對應的值時就會出問題，你只有記錄下標，才可以做到對應位置值得交換，
遞回圖解
挖坑法
挖坑法的單趟排序的基本步驟如下：
1.先選取一個初始坑位，并讓此位置的值記作key（一般選取最左邊或者最右邊）
2.同樣這里也是right先走，直到找到一個比key小的值，然后將這個值填入坑位，并讓這個位置再來做坑，之后移動left，直到找到一個比key大的值，再將這個位置的值填入坑位，然后讓這個位置來做坑，這樣一直回圈下去，直到left==right，
3.當left與right相遇時，此時將key的值賦值給相遇位置即可，這時就達到我們想要的效果：key左邊的值都小于key，key右邊的值都大于key，
4.然后仍然是遞回其左序列和右序列，最終整個序列升序，
代碼實作
//快速排序 （填坑法）
void QuickSort2(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int begin = left; //保存left的值，為了下面的遞回傳遞
int end = right;//保存right的值，為了下面的遞回傳遞
/*int key = left;*/ //這個地方要記住那個數，因為記下標
//的話，沒用，left已經和其他位置交換過了，那么就不是我們想要的值了
int key = a[left];
int hole = left;
while (left < right)
{
while (left<right&&a[right]>=key)
{
--right;
}
a[hole] = a[right];
hole = right;
while (left<right&&a[left]<=key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
int meet = left;
a[meet] = key;
QuickSort2(a, begin, meet- 1);
QuickSort2(a, meet+ 1, end);
}
注意：
1.這里同樣也要保存下left和right的值，原因同Hoare法的一樣，因為代碼程序中其值發生改變會影響遞回傳遞，
2.這里與Hoare法有所不同，這里key要記錄a[left],而不是下標，因為你在之后的填坑程序中，left下標處的值可能被交換了，不是我們最初想要的值，所以要記錄下來最初的那個值，即a[left]，
遞回圖解
前后指標法
前后指標法的單趟排序的基本步驟如下：
1.選出一個key作為比較值，一般是最左或者最右邊，讓prev指向left，cur指向left+1，
2.之后比較cur位置的值和key的值，首先要保證cur位置的值要小于key，而且++prev！=cur,這時交換prev和cur位置對應的值，不管滿不滿足這兩個條件，cur都要++，這樣才能迭代起來，
3.直到cur越界，此時prev為key應該在的位置，此時交換prev位置的值和key，就可以達到我們想要的效果，
4.仍然是遞回其左序列和右序列，最終整個序列有序，
代碼實作
//快速排序（前后指標法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//這里沒有必要記錄left和right的值，因為整個代碼中這兩個量一開始是什么值，最終仍然是那個值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left; //這里要記住小標，不然值是交換不過去的，一般快排中用到交換的換，都是記錄下標
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
注意：
1.這里沒有必要再和上面一樣保存left和right的值了，因為整個程序中left和right的值并沒有變化，
2.這里和Hoare法那兒一樣，key要記錄left這個下標，而不是a[left]這個值，因為你之后要交換meet和key位置處對應的值，而你一開始如果記錄a[left]是做不到這一點的，(一般而言如果有swap交換這個需求的話，都要記錄下標，而不是下標處對應的值）
3.這里要注意a[cur] < a[key] && ++pre != cur這兩個條件寫的先后順序，一定要把比較大小寫在前面，如果你的a[cur]都不滿足比a[key]小，那么就不需要++prev這一步的判斷了，
遞回圖解
非遞回實作
當我們需要將一個用遞回實作的演算法改為非遞回時，一般需要借用一個資料結構，那就是堆疊，將Hoare版本、挖坑法以及前后指標法的快速排序改為非遞回版本，其實主體思想一致，只是呼叫的單趟排序的演算法不同而已，
Hoare版本
//快速排序（前后指標法）
void QuickSort3(int *a, int left, int right)
{
if (left >= right)
{
return;
}
//這里沒有必要記錄left和right的值，因為整個代碼中這兩個量一開始是什么值，最終仍然是那個值
//int begin= left;
//int end = right;
int pre = left;
int cur = left + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++pre != cur)
{
swap(&a[pre], &a[cur]);
}
cur++;
}
int meet = pre;
swap(&a[meet], &a[key]);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
}
挖坑法
//挖坑法（單趟排序）
int QuickSort2(int* a, int left, int right)
{
int key = a[left];//在最左邊形成一個坑位
while (left < right)
{
//right向左，找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右，找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇點
a[meeti] = key;//將key拋入坑位
return meeti;//回傳key的當前位置
}
前后指標法
//前后指標法（單趟排序）
int QuickSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//當cur未越界時繼續
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的內容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界時，prev的位置
Swap(&a[keyi], &a[meeti]);//交換key和prev指標指向的內容
return meeti;//回傳key的當前位置
}
快速排序的非遞回演算法基本思路：
1、先將待排序列的第一個元素的下標和最后一個元素的下標入堆疊，
2、當堆疊不為空時，讀取堆疊中的資訊（一次讀取兩個：一個是L，另一個是R），然后呼叫某一版本的單趟排序，排完后獲得了meet的下標，然后判斷meet的左序列和右序列是否還需要排序，若還需要排序，就將相應序列的L和R入堆疊；若不需排序了（序列只有一個元素或是不存在），就不需要將該序列的資訊入堆疊，
3、反復執行步驟2，直到堆疊為空為止，
非遞回快排代碼實作
//類似于二叉樹的遍歷，根——右子樹——左子樹
void QuickSort4(int* a, int left, int right)
{
ST p;
StackInit(&p);
StackPush(&p, left);
StackPush(&p, right);
while (!StackEmpty(&p))
{
int right= StackTop(&p); //注意堆疊的性質，或進先出，因此先賦值給right
StackPop(&p);
int left= StackTop(&p);
StackPop(&p);
//if (left >= right) 可寫可不寫
//{
// return;
//}
int meet = QuickSort5(a, left, right);
if (left < meet - 1) //左序列還存在時
{
StackPush(&p, left);
StackPush(&p, meet - 1);
}
if (meet + 1 < right) //右序列還存在時
{
StackPush(&p, meet + 1);
StackPush(&p, right);
}
}
StackDestory(&p);
}
注意：這里要注意堆疊的性質后進先出，因此要先賦值給right再賦值給left，
圖解代碼
時間復雜度：O（nlogn）
快速排序的兩個優化
1.三數取中
快速排序的時間復雜度是O(NlogN)，是我們在理想情況下計算的結果，在理想情況下，我們每次進行完單趟排序后，key的左序列與右序列的長度都相同：
?若每趟排序所選的key都正好是該序列的中間值，即單趟排序結束后key位于序列正中間，那么快速排序的時間復雜度就是O(NlogN)，
但是萬一當待排序列本就是一個有序的序列時，我們若是依然每次都選取最左邊或是最右邊的數作為key，那么快速排序的效率將達到最低：
這時的時間復雜度為O（n^2)，其實，對快速排序效率影響最大的就是選取的key，若選取的key越接近中間位置，則則效率越高，
為了避免這種極端情況的發生，于是出現了三數取中：
三數取中，當中的三數指的是：最左邊的數、最右邊的數以及中間位置的數，三數取中就是取這三個數當中，值的大小居中的那個數作為該趟排序的key，這就確保了我們所選取的數不會是序列中的最大或是最小值了，
代碼實作
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2; //防止整形溢位
if (a[right] > a[mid])
{
if (a[mid] > a[left])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[left] > a[mid])
{
return mid;
}
else if (a[right] > a[left])
{
return right;
}
else
{
return left;
}
}
}
2.小區間的優化
我們可以看到，就算是上面理想狀態下的快速排序，也不能避免隨著遞回的深入，每一層的遞回次數會以2倍的形式快速增長，
為了減少遞回樹的最后幾層遞回，我們可以設定一個判斷陳述句，當序列的長度小于某個數的時候就不再進行快速排序，轉而使用其他種類的排序，小區間優化若是使用得當的話，會在一定程度上加快快速排序的效率，而且待排序列的長度越長，該效果越明顯，
代碼實作
//快速排序的小區間優化
void QuickSort6(int *a, int left, int right)
{
if (left >= right)
{
return;
}
if (right - left + 1 > 20)
{
int meet = QuickSort5(a, left, right);
QuickSort5(a, left, meet - 1);
QuickSort5(a, meet + 1, right);
}
else
{
ShellSort(a,right-left+1);
}
}
歸并排序
歸并排序是采用分治法的一個非常典型的應用，其基本思想是：先讓每個子序列都有序，然后再合并這些子序列，讓整個序列有序，這其中要注意了：
子序列又可以看成是一個整體又可以分成兩個子序列，要直到分到序列只有一個數時，這時才不能繼續分了，且當只有一個數時，這個序列就是有序的，其實這兒的思想和二叉樹的好像，當你看完代碼和遞回程序后，你還會發現其實這個和二叉樹的后序遍歷很相似，
下面來看個例子：
其實這張圖就相當于是整個遞回的程序，分解的程序相當于遞回的順序執行，合并的程序相當于遞回回傳的程序，
遞回實作
其間我們需要申請一個與待排序列大小相同的陣列用于合并程序兩個有序的子序列，合并完畢后再將資料拷貝回原陣列，
void MergeSort(int* a, int left, int right,int* temp)
{
if (left >= right)
return;
int mid = left + (right - left) / 2;
int begin1 = left, end1 = mid;
int begin2 = mid+1, end2 = right;
int i = left,j=0; //i一定要寫成left不能寫成0，如果是遞回左序列還可以適用，但是遞回到右序列時就不行了
MergeSort(a, left, mid, temp); //這里要注意區間的劃分，不然可能出現死遞回
MergeSort(a, mid + 1, right, temp);
while (begin1 <= end1&&begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
temp[i++] = a[begin2++];
}
for (j = left; j < right + 1; j++)
{
a[j] = temp[j];
}
}
時間復雜度 ： O（NlogN） 空間復雜度： O（N）
遞回圖解
區間劃分要注意（死遞回）
在上面的代碼中，我們將區間劃分成了[left,mid]和[mid+1，right],是不是只能這樣分了？帶著這樣的好奇，我嘗試了另一種分法，將區間劃分成[left,mid-1]和[mid,right],這樣劃分是否可以了？經過畫圖分析后，答案是不可以的，在這個問題中，區間只能這么劃分，
如果你是這樣劃分的話，在某些測驗用例中，可能會出現死遞回，其原因是你的mid和right有可能永遠不會相等，也就無法結束掉某個遞回，因此造成了死遞回，
非遞回實作
歸并排序的非遞回并不像快速排序那樣一定要用堆疊來實作，我們只需要控制每次參與合并的元素個數即可，最終便能使序列變為有序
這只是一個理想化的例子，在做這種題目時，我們一定要充分考慮到邊界情況，
情況一：
第二個小區間存在，但是個數不滿，這時我們需要對邊界進行控制，不然會導致序列合并時陣列越界的問題，
情況二：
第二個小區間不存在，第一個小區間存在，這時我們不需要在意第一個小區間有沒有滿，因為這時只有一個區間，無法進行序列的合并，所以直接不管它，即break出去就行，
代碼實作
void _MergeSort(int *a, int begin1,int end1,int begin2,int end2, int * temp)
{
int j = begin1;
int i = begin1;
while (begin1 <= end1&&begin2 <= end2) //用&&鏈接，其中有一個結束就結束了
{
if (a[begin1] < a[begin2])
{
temp[i++] = a[begin1++];
}
else
{
temp[i++] = a[begin2++];
}
}
while (begin1 <= end1) //如果區間一還有則全部賦值過去
{
temp[i++] = a[begin1++];
}
while (begin2 <= end2) //如果區間二還有則全部賦值過去，這時兩個序列合并完成
{
temp[i++] = a[begin2++];
}
for (; j <= end2; j++) //將合并好的序列傳給原陣列
{
a[j] = temp[j];
}
}
void MergeSort2(int *a, int n)
{
int *temp = (int *)malloc(sizeof(int)*n);
if (temp == NULL)
{
printf("malloc failed\n");
exit(-1);
}
int gap = 1; //控制每次元素的個數
int i = 0;
while (gap < n)
{
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + (2 * gap) - 1;
if (begin2 >= n) //此時只有第一個區間，不存在兩個序列合并的需求，因此直接break
{
break;
}
if (end2 >= n) //此時第二個區間元素個數不滿，為了防止合并兩個序列時陣列訪問越界，在這里處理掉
{
end2 =n-1;
}
_MergeSort(a, begin1, end1, begin2, end2, temp);
}
gap *= 2;
}
free(temp);
}
遞回圖解
計數排序
計數排序又叫非比較排序，它不需要比較就可以排序，是不是很神奇了？它主要是利用哈希映射來實作的（這在之后c++部分會詳細介紹），這里大概說下它的思路：
1.首先創建一個陣列，那么這個陣列的大小怎么定了？這取決于原陣列中的最大值和最小值，
2.然后我們遍歷原陣列，遇到哪個值則在創建的陣列中以他為下標的位置++，
3.最后列印創建的陣列的下標，那個下標存放的值為幾，則那個下標就列印幾次，
注意：為什么我們這樣就能保證陣列是有序的了？其實最主要的原因是因為陣列的下標本來就是有序的，其次這其中利用了哈希映射，
絕對映射和相對映射
上列中的映射方法稱為絕對映射，即arr陣列中的元素是幾就在count陣列中下標為幾的位置++，但這樣會造成空間浪費，例如，我們要將陣列：1001,1002,1005，進行排序，難道我們要開辟1006個整型空間嗎？
所以我們使用計數排序時，最好是使用相對映射，下面我們來簡單介紹下相對映射：陣列中的最小值就相對于count陣列中的0下標，陣列中的最大值就相對于count陣列中的最后一個下標，這樣，對于陣列1001,1002,1005我們只需要開辟5個空間即可，即此時count陣列中下標為i的位置，記錄的是1001+i出現的次數，
總的來說：
絕對映射：count陣列中下標為i的位置記錄的是arr陣列中數字i出現的次數，
相對映射：count陣列中下標為i的位置記錄的是arr陣列中數字min+i出現的次數，
這里也要注意：計數排序針對數字較為集中時處理比較高效，如果剛剛那個陣列為1,100,1005則不管使用什么映射，都會存在空間的浪費，
代碼實作
//計數排序
void CountSort(int*a, int sz)
{
int min = a[0], max = a[0];
int i = 0;
int j = 0;
for (i = 1; i < sz; i++)
{
if (a[i] < min)
{
min = a[i];
}
if (a[i]>max)
{
max = a[i];
}
}
int range = max - min + 1;//min和max之間的自然數個數（包括min和max本身）
int *count = (int*)calloc(range, sizeof(int));//min和max之間的自然數個數（包括min和max本身）
if (count == NULL)
{
printf("calloc failed\n");
exit(-1);
}
統計相同元素出現次數（相對映射）
for (i = 0; i < sz; i++)
{
count[a[i]-min]++;
}
根據統計結果將序列回收到原來的序列中
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i+min;
}
}
free(count);
}
時間復雜度：O(n+range) 空間復雜度：O（range)
八大排序性能測驗
要想測驗各個排序的性能，首先我們要保證給的資料的公平性，因為我們采用隨機陣列的方式，注意用完之后要釋放，不然會記憶體泄漏，在測驗的時候因為我們給的資料量都是很大的，為了不讓我們等待太久，最好是使用Release版本測驗，
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);
int* a8 = (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];
a8[i] = a1[i];
}
//為了防止給的亂數相對集中或者重復時計數排序的效率不真實
a7[0] = 0;
a7[10000] = 10000;
//這里最好將計數排序寫在前面
/*int begin7 = clock();
CountSort(a7, N);
int end7 = clock();*/
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();
BubbleSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort1(a5,0,N - 1);
int end5 = clock();
int begin6 = clock();
MergeSort2(a6, N);
int end6 = clock();
int begin8 = clock();
HeapSort(a8, N);
int end8 = clock();
/*printf("CountSort:%d\n", end7 - begin7);*/
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("BubbleSort:%d\n", end4 - begin4);
printf("QuickSort1:%d\n", end5 - begin5);
printf("MergeSort2:%d\n", end6 - begin6);
printf("HeapSort:%d\n", end8 - begin8);
free(a7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a8);
}
注意：這里并沒有測驗計數排序，因為計數排序要單獨來出來測驗，放在一起測驗，可能會出問題，
多測驗幾組后發現，快速排序基本都是最快的，這也是為什么人家敢叫快速排序的原因，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/301321.html
標籤：其他