柚子快報激活碼778899分享：數(shù)據(jù)結構——排序算法
柚子快報激活碼778899分享：數(shù)據(jù)結構——排序算法
目錄
目錄
排序
常見排序
常見排序算法的實現(xiàn)
教學意義的排序
冒泡排序
選擇排序
重要排序
插入排序
希爾排序?
?編輯
堆排序
快速排序
hoare法
挖坑法
前后指針法
整體實現(xiàn)
快排優(yōu)化
非遞歸實現(xiàn)
快排總結
歸并排序
遞歸實現(xiàn)
非遞歸實現(xiàn)
歸并排序總結
非比較排序
計數(shù)排序
總結各大排序
萬字解析各大排序，帶你領略你未曾了解的細節(jié)。
排序
排序：排序就是使一串記錄按照其中某個或者某些關鍵字的大小，遞增或者遞減排序起來的操作。 穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。（相同元素的相對順序不發(fā)生改變）
內部排序：數(shù)據(jù)元素全部放在內存中的排序。外部排序：數(shù)據(jù)元素太多不能同時放在內存中，根據(jù)排序過程的要求不斷地在內外存之間移動數(shù)據(jù)的排序。
常見排序
??
常見排序算法的實現(xiàn)
教學意義的排序
冒泡排序
冒泡排序（Bubble Sort）是一種簡單的排序算法，它重復地遍歷要排序的數(shù)列，以升序為例，一次比較兩個元素，如果它們的順序錯誤（前一個元素大于后一個元素）就把它們交換過來。遍歷數(shù)列的工作是重復地進行直到沒有再需要交換，也就是說該數(shù)列已經排序完成。??
這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數(shù)列的頂端。
?//冒泡排序
void BubbleSort(int* arr, int n)
{
for (int j = 0; j < n; j++)
{
// 提前退出冒泡循環(huán)的標志位
bool flag = true;
for (int i = 0; i < n - 1 - j; i++)
{
if (arr[i] > arr[i + 1])
{
Swap(&arr[i], &arr[i + 1]);
flag = false;
}
}
// flag為真，說明在這一輪排序中沒有交換過，說明數(shù)組已經有序，可以提前退出
if (flag) break;
}
}
?
?冒泡排序是一種穩(wěn)定的算法。
時間復雜度：O(n^2)空間復雜度：O(1)
選擇排序
基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序數(shù)據(jù)元素排完 。
每次只選出一個最小元素效率有點低，所以一般都是一趟遍歷同時選出該范圍內最小或者最大的元素。
//選擇排序
void SelectSort(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
//找小
if (arr[i] < arr[mini])
mini = i;
//找大
if (arr[i] > arr[maxi])
maxi = i;
}
//交換
Swap(&arr[begin], &arr[mini]);
//如果begin == maxi，記得更新下標，不然排序會錯亂
if (begin == maxi)
maxi = mini;
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
這里要說明下begin == maxi的情況，其實就是begin位置的元素就是循環(huán)范圍內最大的元素。
Swap(&arr[begin], &arr[mini])后，maxi對應的元素被交換到mini的位置，所以必須更新maxi，不然排序就出現(xiàn)錯誤了。
選擇排序是一種不穩(wěn)定的算法。
?Swap(&arr[begin], &arr[mini])后，元素5的相對順序被破壞了。
時間復雜度：最好最壞都是O(n^2)空間復雜度：O(1)
重要排序
插入排序
基本思想：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為 止，得到一個新的有序序列 。
插入排序就類似于我們打牌時整理撲克牌的操作
算法描述：
從第一個元素開始，假設其有序。（默認升序）取出下一個元素為新元素，與已經有序的元素序列從后往前一一比較。如果有序元素序列的元素大于新元素，將該元素（有序）移到下一個位置。重復步驟3，直到有序元素小于或者等于新元素。將新元素插入到有序元素的下一位置。
//插入排序
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
//[0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tep = arr[end + 1];
while (end >= 0)
{
if (tep < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tep;
}
}
元素集合越接近有序，直接插入排序算法的時間效率越高。
插入排序是一種穩(wěn)定的算法。
?tep < arr[end] 這里不能是<=，如果帶了=，新元素等于有序元素時，有序元素會被挪到下一個位置，相對順序就被破壞了。
時間復雜度：最好是O(n)，最壞是O(n^2)空間復雜度：O(1)
希爾排序?
希爾排序（Shell Sort）是插入排序的一種高效版本，由 Donald Shell 在 1959 年提出。它通過引入一個“增量”的概念來改進插入排序的性能，特別是對于大范圍的元素排序。
基本思想：
增量序列：選擇一個增量序列，這個序列的元素逐漸減小到 1。常見的增量序列有 n/2、n/4、... 直到 1，其中 n 是數(shù)組的長度。 分組處理：按照當前增量值，將數(shù)組分成若干組。 對每組進行插入排序：在每組中，對元素進行插入排序，使得同一組內的元素有序。 縮小增量：將增量減?。ㄍǔＪ菧p半），并重復步驟 2 和 3，直到增量值為 1。 完成排序：當增量為 1 時，整個數(shù)組只包含一個組，此時對整個數(shù)組進行一次插入排序，完成排序過程。
?所以簡單來說，希爾排序是通過該增量對元素序列進行一定程度的預排序，讓該元素序列變得接近有序，當增量為1時，就是進行一趟簡單的插入排序；希爾排序相較于普通的插入排序，元素間的比較和移動更加分散，減少了整個數(shù)組的比較次數(shù)，從而提高了排序效率。
//希爾排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
// +1保證最后一個gap一定是1
// gap > 1時是預排序
// gap == 1時是插入排序
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tep = arr[end + gap];
while (end >= 0)
{
if (tep < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tep;
}
}
}
希爾排序的時間復雜度卻決于增量序列的選擇，好的情況接近O(nlogn)，壞的情況為O(n^2)。
希爾排序是一個不穩(wěn)定的算法，原因在于預排序可能造成相同元素的相對位置改變。
時間復雜度：大約在O(n^1.3)空間復雜度：O(1)
堆排序
堆排序利用了特殊的二叉樹結構--堆（Heap）來實現(xiàn)。
基本思想：
建堆，升序建大堆，降序建小堆。以升序建大堆為例，堆頂元素與最后一個元素交換，縮小堆的范圍（刪除最后一個元素），然后調整剩余元素使其還是一個大堆。重復步驟2，直到所有元素排列完畢。
調整算法一般使用向上調整或者向下調整，這兩個算法都要求根節(jié)點的左右子樹都是有序的（大堆或者小堆）
?
//向下調整
void AdjustDown(int* arr, int size, int parent)
{
int child = 2 * parent + 1;
while (child < size)
{
if (child + 1 < size && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* arr, int size)
{
//向下建堆
//升序 建大堆
//降序 建小堆
for (int i = (size - 2) / 2; i >= 0; i--)
{
AdjustDown(arr, size, i);//大堆
}
int end = size - 1;
while (end > 0)
{
Swap(&arr[end], &arr[0]);
AdjustDown(arr, end, 0);
end--;
}
}
?
堆排序是一個不穩(wěn)定的算法，原因在于向下建堆可能會破壞相同元素的相對位置
堆排序的總時間復雜度是 O(n)（構建堆）+ O(nlogn)（堆排序過程），結果是 O(nlogn)。
時間復雜度：最好最壞都是O(nlogn)空間復雜度：O(1)
快速排序
快速排序（Quick Sort）是一種高效的排序算法，由Hoare 在 1960 年提出。它的基本思想是通過分治法（Divide and Conquer）對數(shù)據(jù)集進行排序。
基本思想：
選擇基準值：從數(shù)列中選擇一個元素作為基準值（key），通常選擇首元素、末元素、中間元素或隨機元素。 分區(qū)操作：重新排列數(shù)列，所有比基準值小的元素放在基準前面，所有比基準值大的元素放在基準后面。在這個分區(qū)退出之后，基準值就處于數(shù)列的中間位置，稱為分區(qū)點。 遞歸排序：遞歸地將小于基準值的子數(shù)列和大于基準值的子數(shù)列進行同樣的排序操作。 完成排序：重復步驟2和3，直到所有子數(shù)列的長度為零或一，這時數(shù)列已經完全排序。
?右邊找小于基準的元素，左邊找大于基準值的元素。
實現(xiàn)快排有幾種不同的方法。
hoare法
實現(xiàn)步驟：
定義兩指針L和R，分別指向元素序列的開頭和結尾。R先出發(fā)，尋找比基準值（key）小的值。L后出發(fā)，尋找比基準值（key）大的值。交換L和R對應的元素。相遇后，將基準值與相遇位置的元素交換。
這里就有個問題，為什么相遇位置的值一定比基準值??？
左邊做key，讓右邊先走，那相遇位置就會比key小。原因如下：
1.如果R遇上L，R走時在找比基準值小的元素，找不到，此時已經遇上了L，L位置的元素此時已經比基準值小（由于上一輪的交換）。
2.如果是L遇上R，注意，R先于L出發(fā)并且已經停住了（R找到比基準值小的元素就會停下），相遇位置的元素就比基準值小。
綜上，L和R的相遇位置的元素一定比基準值小。
//快速排序 hoare
int PartSort1(int* arr, int left, int right)
{
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
//右邊找小
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
//左邊找大
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[keyi], &arr[begin]);
return begin;
}
挖坑法
挖坑法就是Hoare法的優(yōu)化版本，優(yōu)勢在于不用考慮相遇位置元素與基準值的大小。
基本思路：
先將基準值（key）保存，將其位置設置成一個坑位（hole）。R先出發(fā)，尋找比基準值小的值，將其保存在坑位，當前位置設置成新坑位。L后出發(fā)，尋找比基準值大的值，將其保存在坑位，當前位置設置成新坑位。相遇后將關鍵值（key）保存在坑位即可。
//快速排序 挖坑法
int PartSort3(int* arr, int left, int right)
{
int hole = left;//坑位下標
int key = arr[hole];
int begin = left, end = right;
while (begin < end)
{
//右邊找小
while (begin < end && arr[end] >= key)
{
end--;
}
arr[hole] = arr[end];
hole = end;
//左邊找大
while (begin < end && arr[begin] <= key)
{
begin++;
}
arr[hole] = arr[begin];
hole = begin;
}
arr[hole] = key;
return begin;
}
由于，L先走的時候，R必定是坑位，所以L遇到R，相遇位置必定是坑位。（反之同理）
所以相遇位置必定是坑位，即left == hole? == right，最后返回基準值下標hole（begin）。
前后指針法
基本思路：
cur從左邊出發(fā)，prev從cur + 1的位置出發(fā)cur先出發(fā)尋找比key小的值，找到后++prev，cur和prev位置的值進行交換。cur找到比key大的值，++cur。
?解釋：prev要么跟著cur，也就是prev下一個就是cur；或者prev和cur間隔一段比基準值大的區(qū)間。這樣就是達到prev這個位置的元素比基準值大并交換的目的，又排除了prev元素比基準值小的情況（不會影響想要的目的）
?
//快速排序 前后指針
int PartSort2(int* arr, int left, int right)
{
int keyi = left;
int prev = left, cur = prev + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
?
整體實現(xiàn)
//快速排序 hoare
int PartSort1(int* arr, int left, int right)
{
int midi = GetMidi(arr, left, right);
Swap(&arr[left], &arr[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
//右邊找小
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
//左邊找大
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[keyi], &arr[begin]);
return begin;
}
//快速排序 挖坑法
int PartSort3(int* arr, int left, int right)
{
int midi = GetMidi(arr, left, right);
Swap(&arr[left], &arr[midi]);
int hole = left;//坑位下標
int key = arr[hole];
int begin = left, end = right;
while (begin < end)
{
//右邊找小
while (begin < end && arr[end] >= key)
{
end--;
}
arr[hole] = arr[end];
hole = end;
//左邊找大
while (begin < end && arr[begin] <= key)
{
begin++;
}
arr[hole] = arr[begin];
hole = begin;
}
arr[hole] = key;
return begin;
}
//快速排序 前后指針
int PartSort2(int* arr, int left, int right)
{
int midi = GetMidi(arr, left, right);
Swap(&arr[left], &arr[midi]);
int keyi = left;
int prev = left, cur = prev + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
if ((right - left + 1) < 10)
{
InsertSort(arr + left, right - left + 1);
}
else
{
// [left, keyi-1] keyi [keyi+1, right]
int keyi = PartSort1(arr, left, right);
//PartSort2
//PartSort3
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}
快排優(yōu)化
快排在平均情況下具有很好的性能，在某些情況下，性能會退化。
基準值選擇不佳：如果總是選擇極端值（如數(shù)組的第一個元素或最后一個元素）作為基準值，而數(shù)組已經有序或接近有序，這可能導致每次分區(qū)都非常不平衡。 數(shù)組有序或接近有序：快速排序在數(shù)組已經排序或逆序的情況下性能最差，因為每次分區(qū)只能將一個元素放到正確的位置，導致遞歸樹的深度為 O(n)，從而使時間復雜度退化到 O(n^2)。
造成快排性能退化的原因主要是傳遞的（left、right）區(qū)間不合理導致了遞歸深度過深，從而是遞歸的時間復雜度變大（由O(logn)退化到O(n)），最后是整體的性能退化。所以我們的優(yōu)化都是優(yōu)化遞歸的區(qū)間。
優(yōu)化方法：
1.三數(shù)取中
讓基準值選的不那么極端，從而導致區(qū)間分配不平衡。
//三數(shù)取中
int GetMidi(int* arr, int left, int right)
{
int midi = (left + right) / 2;
if (arr[left] < arr[midi])
{
if (arr[midi] < arr[right])
return midi;
//arr[midi] >= arr[right]
if (arr[left] > arr[right])
return left;
else
return right;
}
else//arr[left] >= arr[midi]
{
if (arr[midi] > arr[right])
return midi;
//arr[midi] <= arr[right]
if (arr[left] > arr[right])
return right;
else
return left;
}
}
2.小區(qū)間優(yōu)化
理想情況下的遞歸可以想象成一顆滿二叉樹，最后一次的遞歸占據(jù)總遞歸次數(shù)的一半，所以當區(qū)間少于閾值時就直接插入排序。
非遞歸實現(xiàn)
遞歸實現(xiàn)快排還是不可避免的會遇到很多問題，如效率問題、遞歸深度過深造成的棧溢出問題。那我們就可以嘗試就遞歸改成非遞歸（迭代）。
一般我們使用棧來實現(xiàn)。
//快速排序 非遞歸
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
//入棧其實相當于調用一次函數(shù)
int begin = STTop(&st);//left
STPop(&st);
int end = STTop(&st);//right
STPop(&st);
int keyi = PartSort1(arr, begin, end);
//分割區(qū)間
// [begin, keyi-1] keyi [keyi+1, end]
//先入右邊再入左邊
//等下先取到左邊
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
快排總結
快速排序是一個不穩(wěn)定的算法。
時間復雜度：平均情況下O(nlogn)，最壞的情況下會退化成O(n^2)。空間復雜度：卻決于遞歸深度，一般O(logn)，壞的情況O(n)。
歸并排序
基本思想：
分解：將原始數(shù)組分成更小的數(shù)組，直到每個小數(shù)組只有一個元素。這是通過遞歸實現(xiàn)的，每次將數(shù)組從中間分成兩半。 定義基準情況：遞歸的基準情況是數(shù)組的大小為 1，此時數(shù)組已經排序，因為只有一個元素。 合并：將分解得到的有序小數(shù)組兩兩合并成更大的有序數(shù)組。這是通過比較兩個數(shù)組中元素的大小，并按照順序將它們放入新數(shù)組來實現(xiàn)的。 遞歸合并：重復合并步驟，直到所有的元素合并成一個有序的大數(shù)組。 完成排序：當所有元素都合并到一個數(shù)組中時，整個數(shù)組就完成了排序。
遞歸實現(xiàn)
基本步驟：
1.建立一個等長的臨時數(shù)組，方便后序操作。
2.遞歸拆解區(qū)間，每次一分為二，直到區(qū)間大小為1.
3.分解得到的小數(shù)組比較合并成有序的數(shù)組，然后拷貝回去。
//子歸并
void _MergeSort(int* arr, int* tmp, int begin, int end)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
// 如果[begin, mid][mid+1, end]有序就可以進行歸并了
_MergeSort(arr, tmp, begin, mid);
_MergeSort(arr, tmp, mid + 1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//歸并排序
void MergeSort(int* arr, int n)
{
int* tep = (int*)malloc(sizeof(int) * n);
if(tep == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(arr, tep, 0, n - 1);
free(tep);
tep = NULL;
}
這里有個值得注意的點，分割區(qū)間是不能以[begin, mid-1][mid, end]這樣分割的。
以[begin, mid-1][mid, end]這樣分割區(qū)間就會導致某些情況下，分割出的左區(qū)間不存在，右區(qū)間跟原來一樣，從而導致不斷遞歸然后棧溢出。
所以分割區(qū)間必須以[begin, mid][mid+1, end]這樣分割。
非遞歸實現(xiàn)
不能棧模擬的原因：
這里的非遞歸實現(xiàn)就不太適合用棧去模擬實現(xiàn)了，因為首先需要對區(qū)間進行分割，直到區(qū)間大小為1，然后進行歸并，歸并這個過程是需要倒回去對各個區(qū)間（原始區(qū)間、分割出來的區(qū)間）進行處理的，用棧模擬這個過程分割區(qū)間是不可逆的，你沒有辦法獲取當前區(qū)間的父區(qū)間進行歸并（沒有辦法確定當前區(qū)間是哪個區(qū)間分割出來的，因為除法會丟數(shù)據(jù)）。
所以我們直接用迭代進行模擬實現(xiàn)就可以了。
使用一個gap代表歸并每組的數(shù)據(jù)個數(shù)。
void MergeSortNonR(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// gap 每組歸并數(shù)據(jù)的數(shù)據(jù)個數(shù)
int gap = 1;
while (gap < n)
{
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;
// 1.第一組沒越界，第二組越界不存在，不需要歸并
// 2.第一組end1越界了，那么第二組肯定越界，不需要歸并
//上面兩種情況合二為一，就只需要判斷第二組越界就可以了。
if (begin2 >= n)
break;
// 第二的組begin2沒越界，end2越界了，需要修正一下，繼續(xù)歸并
if (end2 >= n)
end2 = n - 1;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] <= arr[begin2])
{
tmp[j++] = arr[begin1++];
}
else
{
tmp[j++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
歸并排序總結
歸并排序是一個穩(wěn)定的算法。
時間復雜度：最好最壞的都是O(nlogn)空間復雜度：O(n)
非比較排序
非比較排序算法是基于數(shù)據(jù)的其他屬性或次序標準進行排序的算法，而不是基于元素之間的比較，這種排序在特定場景會很高效。
非比較排序包括：
計數(shù)排序（Counting Sort）： 適用于整數(shù)且整數(shù)的范圍不是很大。通過統(tǒng)計每個元素出現(xiàn)的次數(shù)，然后按順序構造最終的排序結果。 基數(shù)排序（Radix Sort）： 可以處理整數(shù)、浮點數(shù)或字符串。按照低位到高位的順序，逐位進行排序。 桶排序（Bucket Sort）： 適用于均勻分布的數(shù)據(jù)。將數(shù)據(jù)分配到有限數(shù)量的“桶”中，每個桶內的數(shù)據(jù)使用其他排序算法進行排序，然后按順序合并桶中的數(shù)據(jù)。 位圖排序： 使用位圖來表示數(shù)據(jù)項的存在或不存在，然后對位圖進行處理，得到排序結果。 排序網絡（Sorting Networks）： 一種硬件排序結構，通過比較-交換網絡實現(xiàn)排序，適用于并行處理。 指數(shù)排序（Exponential Sort）： 基于指數(shù)函數(shù)，適用于部分數(shù)據(jù)已知排序的情況。 鴿巢排序（Nest Sort）： 一種使用“鴿巢原理”的排序方法，適用于小規(guī)模數(shù)據(jù)。
計數(shù)排序
這里我們實現(xiàn)個比較簡單的計數(shù)排序。
計數(shù)排序的基本思想是通過鍵值計數(shù)來對元素進行排序，這種方法特別適用于元素值范圍較小的情況。
步驟：
1.遍歷原數(shù)組，確定最小值和最大值，通過最大值 - 最小值 + 1確定計數(shù)數(shù)組的大小。
2.創(chuàng)建計數(shù)數(shù)組，遍歷原數(shù)組，統(tǒng)計原數(shù)組個元素的出現(xiàn)次數(shù)。（這是一個相對映射，假如數(shù)組中的元素是i，則count[i - min] ++，不走直接映射是為了防止空間浪費）
3.遍歷計數(shù)數(shù)組，通過計數(shù)數(shù)組覆蓋原數(shù)組。
//計數(shù)排序
//時間復雜度（N + Range）
//空間復雜度（range）
//適合整數(shù)，范圍集中的
void CountSort(int* arr, int n)
{
//找最小值和最大值
int max, min;
max = min = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;
int* count = (int*)calloc(range,sizeof(int));
if (count == NULL)
{
perror("calloc fail");
return;
}
//統(tǒng)計次數(shù)
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
free(count);
}
總結：
計數(shù)排序適用于小范圍整數(shù)排序，能在O(n + range)時間內完成排序，range是整數(shù)的范圍。
計數(shù)排序不適用于非整數(shù)，也不適用于range很大的數(shù)據(jù)，因為需要開辟額外的空間。
計數(shù)排序是個穩(wěn)定的算法，因為統(tǒng)計頻率是按順序計數(shù)，按順序覆蓋原數(shù)組。
時間復雜度：O(n + range)空間復雜度：O(range)
總結各大排序
拜拜，下期再見?
摸魚ing???
柚子快報激活碼778899分享：數(shù)據(jù)結構——排序算法
參考閱讀
本文內容根據(jù)網絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯(lián)系刪除。
Miravia出海夢幻購
