柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)——排序算法

http://yzkb.51969.com/

目錄

目錄

排序

常見排序

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

教學(xué)意義的排序

冒泡排序

選擇排序

重要排序

插入排序

希爾排序?

?編輯

堆排序

快速排序

hoare法

挖坑法

前后指針法

整體實(shí)現(xiàn)

快排優(yōu)化

非遞歸實(shí)現(xiàn)

快排總結(jié)

歸并排序

遞歸實(shí)現(xiàn)

非遞歸實(shí)現(xiàn)

歸并排序總結(jié)

非比較排序

計(jì)數(shù)排序

總結(jié)各大排序

萬字解析各大排序，帶你領(lǐng)略你未曾了解的細(xì)節(jié)。

排序

排序：排序就是使一串記錄按照其中某個(gè)或者某些關(guān)鍵字的大小，遞增或者遞減排序起來的操作。 穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。（相同元素的相對順序不發(fā)生改變）

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

常見排序

??

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

教學(xué)意義的排序

冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法，它重復(fù)地遍歷要排序的數(shù)列，以升序?yàn)槔淮伪容^兩個(gè)元素，如果它們的順序錯(cuò)誤（前一個(gè)元素大于后一個(gè)元素）就把它們交換過來。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。??

這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

?//冒泡排序

void BubbleSort(int* arr, int n)

{

for (int j = 0; j < n; j++)

{

// 提前退出冒泡循環(huán)的標(biāo)志位

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ù)組已經(jīng)有序，可以提前退出

if (flag) break;

}

}

?

?冒泡排序是一種穩(wěn)定的算法。

時(shí)間復(fù)雜度：O(n^2)空間復(fù)雜度：O(1)

選擇排序

基本思想：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序數(shù)據(jù)元素排完 。

每次只選出一個(gè)最小元素效率有點(diǎn)低，所以一般都是一趟遍歷同時(shí)選出該范圍內(nèi)最小或者最大的元素。

//選擇排序

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，記得更新下標(biāo)，不然排序會(huì)錯(cuò)亂

if (begin == maxi)

maxi = mini;

Swap(&arr[end], &arr[maxi]);

begin++;

end--;

}

}

這里要說明下begin == maxi的情況，其實(shí)就是begin位置的元素就是循環(huán)范圍內(nèi)最大的元素。

Swap(&arr[begin], &arr[mini])后，maxi對應(yīng)的元素被交換到mini的位置，所以必須更新maxi，不然排序就出現(xiàn)錯(cuò)誤了。

選擇排序是一種不穩(wěn)定的算法。

?Swap(&arr[begin], &arr[mini])后，元素5的相對順序被破壞了。

時(shí)間復(fù)雜度：最好最壞都是O(n^2)空間復(fù)雜度：O(1)

重要排序

插入排序

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

插入排序就類似于我們打牌時(shí)整理撲克牌的操作

算法描述：

從第一個(gè)元素開始，假設(shè)其有序。（默認(rèn)升序）取出下一個(gè)元素為新元素，與已經(jīng)有序的元素序列從后往前一一比較。如果有序元素序列的元素大于新元素，將該元素（有序）移到下一個(gè)位置。重復(fù)步驟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;

}

}

元素集合越接近有序，直接插入排序算法的時(shí)間效率越高。

插入排序是一種穩(wěn)定的算法。

?tep < arr[end] 這里不能是<=，如果帶了=，新元素等于有序元素時(shí)，有序元素會(huì)被挪到下一個(gè)位置，相對順序就被破壞了。

時(shí)間復(fù)雜度：最好是O(n)，最壞是O(n^2)空間復(fù)雜度：O(1)

希爾排序?

希爾排序（Shell Sort）是插入排序的一種高效版本，由 Donald Shell 在 1959 年提出。它通過引入一個(gè)“增量”的概念來改進(jìn)插入排序的性能，特別是對于大范圍的元素排序。

基本思想：

增量序列：選擇一個(gè)增量序列，這個(gè)序列的元素逐漸減小到 1。常見的增量序列有 n/2、n/4、... 直到 1，其中 n 是數(shù)組的長度。 分組處理：按照當(dāng)前增量值，將數(shù)組分成若干組。 對每組進(jìn)行插入排序：在每組中，對元素進(jìn)行插入排序，使得同一組內(nèi)的元素有序。 縮小增量：將增量減?。ㄍǔＪ菧p半），并重復(fù)步驟 2 和 3，直到增量值為 1。 完成排序：當(dāng)增量為 1 時(shí)，整個(gè)數(shù)組只包含一個(gè)組，此時(shí)對整個(gè)數(shù)組進(jìn)行一次插入排序，完成排序過程。

?所以簡單來說，希爾排序是通過該增量對元素序列進(jìn)行一定程度的預(yù)排序，讓該元素序列變得接近有序，當(dāng)增量為1時(shí)，就是進(jìn)行一趟簡單的插入排序；希爾排序相較于普通的插入排序，元素間的比較和移動(dòng)更加分散，減少了整個(gè)數(shù)組的比較次數(shù)，從而提高了排序效率。

//希爾排序

void ShellSort(int* arr, int n)

{

int gap = n;

while (gap > 1)

{

// +1保證最后一個(gè)gap一定是1

// gap > 1時(shí)是預(yù)排序

// gap == 1時(shí)是插入排序

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;

}

}

}

希爾排序的時(shí)間復(fù)雜度卻決于增量序列的選擇，好的情況接近O(nlogn)，壞的情況為O(n^2)。

希爾排序是一個(gè)不穩(wěn)定的算法，原因在于預(yù)排序可能造成相同元素的相對位置改變。

時(shí)間復(fù)雜度：大約在O(n^1.3)空間復(fù)雜度：O(1)

堆排序

堆排序利用了特殊的二叉樹結(jié)構(gòu)--堆（Heap）來實(shí)現(xiàn)。

基本思想：

建堆，升序建大堆，降序建小堆。以升序建大堆為例，堆頂元素與最后一個(gè)元素交換，縮小堆的范圍（刪除最后一個(gè)元素），然后調(diào)整剩余元素使其還是一個(gè)大堆。重復(fù)步驟2，直到所有元素排列完畢。

調(diào)整算法一般使用向上調(diào)整或者向下調(diào)整，這兩個(gè)算法都要求根節(jié)點(diǎn)的左右子樹都是有序的（大堆或者小堆）

?

//向下調(diào)整

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--;

}

}

?

堆排序是一個(gè)不穩(wěn)定的算法，原因在于向下建堆可能會(huì)破壞相同元素的相對位置

堆排序的總時(shí)間復(fù)雜度是 O(n)（構(gòu)建堆）+ O(nlogn)（堆排序過程），結(jié)果是 O(nlogn)。

時(shí)間復(fù)雜度：最好最壞都是O(nlogn)空間復(fù)雜度：O(1)

快速排序

快速排序（Quick Sort）是一種高效的排序算法，由Hoare 在 1960 年提出。它的基本思想是通過分治法（Divide and Conquer）對數(shù)據(jù)集進(jìn)行排序。

基本思想：

選擇基準(zhǔn)值：從數(shù)列中選擇一個(gè)元素作為基準(zhǔn)值（key），通常選擇首元素、末元素、中間元素或隨機(jī)元素。 分區(qū)操作：重新排列數(shù)列，所有比基準(zhǔn)值小的元素放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素放在基準(zhǔn)后面。在這個(gè)分區(qū)退出之后，基準(zhǔn)值就處于數(shù)列的中間位置，稱為分區(qū)點(diǎn)。 遞歸排序：遞歸地將小于基準(zhǔn)值的子數(shù)列和大于基準(zhǔn)值的子數(shù)列進(jìn)行同樣的排序操作。 完成排序：重復(fù)步驟2和3，直到所有子數(shù)列的長度為零或一，這時(shí)數(shù)列已經(jīng)完全排序。

?右邊找小于基準(zhǔn)的元素，左邊找大于基準(zhǔn)值的元素。

實(shí)現(xiàn)快排有幾種不同的方法。

hoare法

實(shí)現(xiàn)步驟：

定義兩指針L和R，分別指向元素序列的開頭和結(jié)尾。R先出發(fā)，尋找比基準(zhǔn)值（key）小的值。L后出發(fā)，尋找比基準(zhǔn)值（key）大的值。交換L和R對應(yīng)的元素。相遇后，將基準(zhǔn)值與相遇位置的元素交換。

這里就有個(gè)問題，為什么相遇位置的值一定比基準(zhǔn)值?。?/p>

左邊做key，讓右邊先走，那相遇位置就會(huì)比key小。原因如下：

1.如果R遇上L，R走時(shí)在找比基準(zhǔn)值小的元素，找不到，此時(shí)已經(jīng)遇上了L，L位置的元素此時(shí)已經(jīng)比基準(zhǔn)值小（由于上一輪的交換）。

2.如果是L遇上R，注意，R先于L出發(fā)并且已經(jīng)停住了（R找到比基準(zhǔn)值小的元素就會(huì)停下），相遇位置的元素就比基準(zhǔn)值小。

綜上，L和R的相遇位置的元素一定比基準(zhǔn)值小。

//快速排序 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)勢在于不用考慮相遇位置元素與基準(zhǔn)值的大小。

基本思路：

先將基準(zhǔn)值（key）保存，將其位置設(shè)置成一個(gè)坑位（hole）。R先出發(fā)，尋找比基準(zhǔn)值小的值，將其保存在坑位，當(dāng)前位置設(shè)置成新坑位。L后出發(fā)，尋找比基準(zhǔn)值大的值，將其保存在坑位，當(dāng)前位置設(shè)置成新坑位。相遇后將關(guān)鍵值（key）保存在坑位即可。

//快速排序 挖坑法

int PartSort3(int* arr, int left, int right)

{

int hole = left;//坑位下標(biāo)

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先走的時(shí)候，R必定是坑位，所以L遇到R，相遇位置必定是坑位。（反之同理）

所以相遇位置必定是坑位，即left == hole? == right，最后返回基準(zhǔn)值下標(biāo)hole（begin）。

前后指針法

基本思路：

cur從左邊出發(fā)，prev從cur + 1的位置出發(fā)cur先出發(fā)尋找比key小的值，找到后++prev，cur和prev位置的值進(jìn)行交換。cur找到比key大的值，++cur。

?解釋：prev要么跟著cur，也就是prev下一個(gè)就是cur；或者prev和cur間隔一段比基準(zhǔn)值大的區(qū)間。這樣就是達(dá)到prev這個(gè)位置的元素比基準(zhǔn)值大并交換的目的，又排除了prev元素比基準(zhǔn)值小的情況（不會(huì)影響想要的目的）

?

//快速排序 前后指針

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;

}

?

整體實(shí)現(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;//坑位下標(biāo)

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)化

快排在平均情況下具有很好的性能，在某些情況下，性能會(huì)退化。

基準(zhǔn)值選擇不佳：如果總是選擇極端值（如數(shù)組的第一個(gè)元素或最后一個(gè)元素）作為基準(zhǔn)值，而數(shù)組已經(jīng)有序或接近有序，這可能導(dǎo)致每次分區(qū)都非常不平衡。 數(shù)組有序或接近有序：快速排序在數(shù)組已經(jīng)排序或逆序的情況下性能最差，因?yàn)槊看畏謪^(qū)只能將一個(gè)元素放到正確的位置，導(dǎo)致遞歸樹的深度為 O(n)，從而使時(shí)間復(fù)雜度退化到 O(n^2)。

造成快排性能退化的原因主要是傳遞的（left、right）區(qū)間不合理導(dǎo)致了遞歸深度過深，從而是遞歸的時(shí)間復(fù)雜度變大（由O(logn)退化到O(n)），最后是整體的性能退化。所以我們的優(yōu)化都是優(yōu)化遞歸的區(qū)間。

優(yōu)化方法：

1.三數(shù)取中

讓基準(zhǔn)值選的不那么極端，從而導(dǎo)致區(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ù)的一半，所以當(dāng)區(qū)間少于閾值時(shí)就直接插入排序。

非遞歸實(shí)現(xiàn)

遞歸實(shí)現(xiàn)快排還是不可避免的會(huì)遇到很多問題，如效率問題、遞歸深度過深造成的棧溢出問題。那我們就可以嘗試就遞歸改成非遞歸（迭代）。

一般我們使用棧來實(shí)現(xiàn)。

//快速排序 非遞歸

void QuickSortNonR(int* arr, int left, int right)

{

ST st;

STInit(&st);

STPush(&st, right);

STPush(&st, left);

while (!STEmpty(&st))

{

//入棧其實(shí)相當(dāng)于調(diào)用一次函數(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);

}

快排總結(jié)

快速排序是一個(gè)不穩(wěn)定的算法。

時(shí)間復(fù)雜度：平均情況下O(nlogn)，最壞的情況下會(huì)退化成O(n^2)?？臻g復(fù)雜度：卻決于遞歸深度，一般O(logn)，壞的情況O(n)。

歸并排序

基本思想：

分解：將原始數(shù)組分成更小的數(shù)組，直到每個(gè)小數(shù)組只有一個(gè)元素。這是通過遞歸實(shí)現(xiàn)的，每次將數(shù)組從中間分成兩半。 定義基準(zhǔn)情況：遞歸的基準(zhǔn)情況是數(shù)組的大小為 1，此時(shí)數(shù)組已經(jīng)排序，因?yàn)橹挥幸粋€(gè)元素。 合并：將分解得到的有序小數(shù)組兩兩合并成更大的有序數(shù)組。這是通過比較兩個(gè)數(shù)組中元素的大小，并按照順序?qū)⑺鼈兎湃胄聰?shù)組來實(shí)現(xiàn)的。 遞歸合并：重復(fù)合并步驟，直到所有的元素合并成一個(gè)有序的大數(shù)組。 完成排序：當(dāng)所有元素都合并到一個(gè)數(shù)組中時(shí)，整個(gè)數(shù)組就完成了排序。

遞歸實(shí)現(xiàn)

基本步驟：

1.建立一個(gè)等長的臨時(shí)數(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]有序就可以進(jìn)行歸并了

_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;

}

這里有個(gè)值得注意的點(diǎn)，分割區(qū)間是不能以[begin, mid-1][mid, end]這樣分割的。

以[begin, mid-1][mid, end]這樣分割區(qū)間就會(huì)導(dǎo)致某些情況下，分割出的左區(qū)間不存在，右區(qū)間跟原來一樣，從而導(dǎo)致不斷遞歸然后棧溢出。

所以分割區(qū)間必須以[begin, mid][mid+1, end]這樣分割。

非遞歸實(shí)現(xiàn)

不能棧模擬的原因：

這里的非遞歸實(shí)現(xiàn)就不太適合用棧去模擬實(shí)現(xiàn)了，因?yàn)槭紫刃枰獙^(qū)間進(jìn)行分割，直到區(qū)間大小為1，然后進(jìn)行歸并，歸并這個(gè)過程是需要倒回去對各個(gè)區(qū)間（原始區(qū)間、分割出來的區(qū)間）進(jìn)行處理的，用棧模擬這個(gè)過程分割區(qū)間是不可逆的，你沒有辦法獲取當(dāng)前區(qū)間的父區(qū)間進(jìn)行歸并（沒有辦法確定當(dāng)前區(qū)間是哪個(gè)區(qū)間分割出來的，因?yàn)槌〞?huì)丟數(shù)據(jù)）。

所以我們直接用迭代進(jìn)行模擬實(shí)現(xiàn)就可以了。

使用一個(gè)gap代表歸并每組的數(shù)據(jù)個(gè)數(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ù)個(gè)數(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.第一組沒越界，第二組越界不存在，不需要?dú)w并

// 2.第一組end1越界了，那么第二組肯定越界，不需要?dú)w并

//上面兩種情況合二為一，就只需要判斷第二組越界就可以了。

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;

}

歸并排序總結(jié)

歸并排序是一個(gè)穩(wěn)定的算法。

時(shí)間復(fù)雜度：最好最壞的都是O(nlogn)空間復(fù)雜度：O(n)

非比較排序

非比較排序算法是基于數(shù)據(jù)的其他屬性或次序標(biāo)準(zhǔn)進(jìn)行排序的算法，而不是基于元素之間的比較，這種排序在特定場景會(huì)很高效。

非比較排序包括：

計(jì)數(shù)排序（Counting Sort）： 適用于整數(shù)且整數(shù)的范圍不是很大。通過統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，然后按順序構(gòu)造最終的排序結(jié)果。 基數(shù)排序（Radix Sort）： 可以處理整數(shù)、浮點(diǎn)數(shù)或字符串。按照低位到高位的順序，逐位進(jìn)行排序。 桶排序（Bucket Sort）： 適用于均勻分布的數(shù)據(jù)。將數(shù)據(jù)分配到有限數(shù)量的“桶”中，每個(gè)桶內(nèi)的數(shù)據(jù)使用其他排序算法進(jìn)行排序，然后按順序合并桶中的數(shù)據(jù)。 位圖排序： 使用位圖來表示數(shù)據(jù)項(xiàng)的存在或不存在，然后對位圖進(jìn)行處理，得到排序結(jié)果。 排序網(wǎng)絡(luò)（Sorting Networks）： 一種硬件排序結(jié)構(gòu)，通過比較-交換網(wǎng)絡(luò)實(shí)現(xiàn)排序，適用于并行處理。 指數(shù)排序（Exponential Sort）： 基于指數(shù)函數(shù)，適用于部分?jǐn)?shù)據(jù)已知排序的情況。 鴿巢排序（Nest Sort）： 一種使用“鴿巢原理”的排序方法，適用于小規(guī)模數(shù)據(jù)。

計(jì)數(shù)排序

這里我們實(shí)現(xiàn)個(gè)比較簡單的計(jì)數(shù)排序。

計(jì)數(shù)排序的基本思想是通過鍵值計(jì)數(shù)來對元素進(jìn)行排序，這種方法特別適用于元素值范圍較小的情況。

步驟：

1.遍歷原數(shù)組，確定最小值和最大值，通過最大值 - 最小值 + 1確定計(jì)數(shù)數(shù)組的大小。

2.創(chuàng)建計(jì)數(shù)數(shù)組，遍歷原數(shù)組，統(tǒng)計(jì)原數(shù)組個(gè)元素的出現(xiàn)次數(shù)。（這是一個(gè)相對映射，假如數(shù)組中的元素是i，則count[i - min] ++，不走直接映射是為了防止空間浪費(fèi)）

3.遍歷計(jì)數(shù)數(shù)組，通過計(jì)數(shù)數(shù)組覆蓋原數(shù)組。

//計(jì)數(shù)排序

//時(shí)間復(fù)雜度（N + Range）

//空間復(fù)雜度（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)計(jì)次數(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);

}

總結(jié)：

計(jì)數(shù)排序適用于小范圍整數(shù)排序，能在O(n + range)時(shí)間內(nèi)完成排序，range是整數(shù)的范圍。

計(jì)數(shù)排序不適用于非整數(shù)，也不適用于range很大的數(shù)據(jù)，因?yàn)樾枰_辟額外的空間。

計(jì)數(shù)排序是個(gè)穩(wěn)定的算法，因?yàn)榻y(tǒng)計(jì)頻率是按順序計(jì)數(shù)，按順序覆蓋原數(shù)組。

時(shí)間復(fù)雜度：O(n + range)空間復(fù)雜度：O(range)

總結(jié)各大排序

拜拜，下期再見?

摸魚ing???

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)——排序算法

http://yzkb.51969.com/

參考閱讀