[數據結構] 萬字解析排序算法
文章目錄
快速排序
快速排序（Quick Sort）是一種高效的排序算法，它利用分治法將一個數組分成兩個子數組，然后遞歸地對這兩個子數組進行排序。在快速排序的每一趟排序中，核心步驟是單趟循環(huán)，這一步驟將數組分成兩分，一部分的所有元素都小于等于一個特定的“基準值”（pivot），另一部分的所有元素都大于基準值。
雙指針法
快速排序邏輯如下GIF：
由此可得，快速排序的單次邏輯代碼實現為：
if (left >= right)
{
return;
}
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
// 左邊找大
// a[end] >= a[keyi] 防止兩個位置相同時一直交換，陷入無限循環(huán)
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 右邊找小
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
/*if (begin < end)
{
Swap(&a[begin], &a[end]);
}*/
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
設置最左邊為keyi，開始從左邊向右找比keyi大的數據，從右邊向左找比keyi小的數據，執(zhí)行邏輯：右邊先進行向左查找小數據，找到后停留在小數據位置，左邊再向右查找大數據，找到后停留。交換找到的兩個位置的數據，繼續(xù)循環(huán)查找然后交換。當兩個指針指向位置相同時將相遇位置與keyi位置交換（此時的相遇位置一定是比keyi小的數據）。
通過分治的思想來進行分組排序。在單趟排序后keyi作為中間值換到了兩個指針上一輪相遇位置，從keyi位置二分數組，將兩個數組的最左邊元素設置為keyi，繼續(xù)進行循環(huán)，繼續(xù)分治，如此最后即達到了整體順序的目的。
整體排序過程整理
選擇基準值（Pivot）
快速排序的第一步是從數組中選擇一個基準值（pivot）。基準值的選擇可以有多種策略，例如選擇第一個元素、最后一個元素、中間的元素，或者隨機選擇。基準值的選擇會影響算法的性能，但不會影響其正確性。
單趟劃分（Partitioning）
在單趟劃分過程中，數組中的元素被重新排序，使得基準值左邊的所有元素都小于等于基準值，右邊的所有元素都大于等于基準值。這個過程可以描述如下：
- 初始化指針：設定兩個指針
begin和end，分別從數組的兩端開始。- 尋找逆序對：從右向左移動
end指針，直到找到一個小于基準值的元素；從左向右移動begin指針，直到找到一個大于基準值的元素。- 交換元素：交換這兩個指針指向的元素。
- 重復：重復上述過程，直到
begin和end相遇。
此時，基準值應插入到數組中間某個位置，使得其左邊的元素全都小于等于它，右邊的元素全都大于等于它。
遞歸分治（Divide and Conquer）
單趟劃分完成后，基準值被放置到其最終位置，且數組被分為兩部分。然后，對這兩部分遞歸地進行快速排序：
- 對左部分排序：對基準值左邊的子數組遞歸調用快速排序。
- 對右部分排序：對基準值右邊的子數組遞歸調用快速排序。
遞歸的終止條件是子數組的大小為零或一，即 left >= right。
終止條件
遞歸過程最終會將所有子數組排序完成，此時整個數組已經排序完成。
合并
快速排序本質上不需要顯式的合并步驟，因為在遞歸的每個步驟中，基準值的左右子數組已經各自有序，整個數組的排序結果自然也就完成了。
整體代碼實現
// 簡單快排
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
// 左邊找大
// a[end] >= a[keyi] 防止兩個位置相同時一直交換，陷入無限循環(huán)
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 右邊找小
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
/*if (begin < end)
{
Swap(&a[begin], &a[end]);
}*/
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
// 現在的begin位置是之前的keyi位置的數據，所以更新
keyi = begin;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
為什么相遇位置一定是小值？
情況 1: 右指針j找到了小于key的元素
- 右指針j移動：從右向左移動，找到第一個小于key的元素，停下。
- 左指針i移動：接著，左指針i從左向右移動，找到第一個大于key的元素，停下。
- 如果i < j，交換i和j指向的元素，然后繼續(xù)移動兩個指針。
- 如果i >= j，停止移動，進行下一步操作。
在此情況下，當兩個指針相遇（i == j）時，此位置的元素是最后一個j找到的小于key的值。因為j停在了小于key的元素上，而i在移動過程中沒有再向右移動（因為i >= j），因此相遇位置的元素一定小于等于key。
情況 2: 右指針j沒有找到小于key的元素
- 右指針j移動：從右向左移動，直到與key相遇（即j移動到數組的開始位置）。
- 左指針i移動：如果j已經與key相遇，那么i也會在開始位置停下。
在這種情況下，j沒有找到任何小于key的元素，意味著所有元素都大于等于key。因此，當i和j相遇時，他們都在數組的起始位置，這時key自己與自己交換，整個數組可能是已經排序的或者所有元素都相等。
總結
在快速排序的每一次循環(huán)中，無論哪種情況，當i和j相遇時，這個位置的元素都是小于等于key的。這是因為j指針的職責是找到小于key的元素，并在找到后停下。如果j在沒有找到小于key的元素前就與i相遇，那么說明這部分元素都大于等于key，相遇點自然也是小于等于key（在情況2中，key與自己交換）。這樣，基準元素key可以在每輪循環(huán)結束時與相遇點的元素交換，確保key左邊的元素不大于它，右邊的元素不小于它，完成一次分區(qū)操作。
挖坑法
int Partition(int* arr, int low, int high) {
int pivot = arr[low]; // 選擇第一個元素作為基準值
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high]; // 用比基準小的記錄替換低位記錄
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low]; // 用比基準大的記錄替換高位記錄
}
arr[low] = pivot; // 基準值歸位
return low; // 返回基準值的位置
}
void QuickSort(int* arr, int low, int high) {
if (low < high) {
int pivotPos = Partition(arr, low, high); // 劃分操作，將數組分為兩部分
QuickSort(arr, low, pivotPos - 1); // 遞歸處理左子序列
QuickSort(arr, pivotPos + 1, high); // 遞歸處理右子序列
}
}
挖坑法的基本邏輯
- 選擇基準值：從待排序數組中選擇一個基準值，通常選擇第一個元素作為基準值。
- 挖坑填數：通過一趟排序將待排序數組分割成獨立的兩部分，分別是比基準值小的元素和比基準值大的元素。這一過程中，使用挖坑的方式進行元素交換，即通過不斷移動元素，將基準值挖成一個坑，然后通過交換操作，將小于基準值的元素填入這個坑中。
- 遞歸處理：對左右兩部分分別遞歸進行上述操作，直到整個序列有序。
為什么最后的坑位一定是key這個中間值
在挖坑法中，最后的坑位置放置基準值（key）的過程保證了左側的元素均小于等于基準值，右側的元素均大于等于基準值。這是因為挖坑填數過程中，每次我們都是先從右側開始查找小于基準值的元素，然后填入左側的坑中，接著從左側開始查找大于基準值的元素，填入右側的坑中，直到左右指針相遇。
當左右指針相遇時，這個位置的元素一定是小于等于基準值的，因為最后一次填坑操作是從右側填入左側的坑，然后左右指針相遇。由于左指針在遇到右指針之前只移動到小于等于基準值的位置，所以最后的坑位置一定是中間值，即小于等于基準值的元素。
因此，挖坑法保證了基準值放置在最終排序后的正確位置，同時確保了左右兩側的元素滿足快速排序的要求，實現了快速排序的劃分過程。
前后指針法
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
// [left, keyi-1] keyi [keyi+1, right]
QuickSortt(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
前后指針法的基本邏輯
- 基準值選取：
- 通過三數取中的方法選擇基準值，將數組中的左端、右端和中間位置的元素進行比較，選取中間值作為基準值。
- 將選取的基準值與數組中的第一個元素交換，以便后續(xù)比較。
- 前后指針交換：
- 使用前后指針方法，前指針
prev初始指向基準值，后指針cur初始指向基準值的下一個位置。cur用來找比基準值小的值，cur作為比基準值大的數據前的分割指針。- 每次
cur先走：
- 當
cur指向大于基準值時，prev先不走，cur繼續(xù)向后走。- 當
cur指向小于基準值時，prev向后走一次，并與cur交換位置（由于上一輪cur遇到大的會直接走，prev會停留，所以prev + 1一定是比基準值大的數據）。- 持續(xù)循環(huán)，當
a[cur] < a[keyi]時，將cur指向的元素與prev后一個位置的元素交換，同時prev向后移動一位。- 繼續(xù)移動
cur指針，直到遍歷完整個數組，cur指向數組最后一個數據后即循環(huán)結束。- 基準值歸位：
- 單趟循環(huán)結束后，此時的
prev指向的一定是比基準值小的數值，所以將基準值a[keyi]與a[prev]交換，將基準值放置在正確的位置。- 遞歸處理：
- 基準值被換到上一趟最后
prev的位置，作為中間值，用基準值將數組分為左右兩部分，分別為[left, keyi-1]和[keyi+1, right]，對這兩部分分別進行遞歸快速排序。- 遞歸結束條件是
left >= right，即子數組只有一個元素或為空時結束遞歸。
遞歸優(yōu)化：三數取中與小區(qū)間優(yōu)化
三數取中 （Median of Three）
原因
三數取中的原因在于快速排序的性能與樞軸選擇密切相關。如果選擇的樞軸能夠將數組均勻地分為兩部分，遞歸的層次會減少，從而提高效率。而極端的樞軸選擇會導致遞歸深度增加，進而導致性能下降。
**極端情況：**如果排序的是一個有序的序列（
left一直是當前分組最小值），每一次從右往左找小時都會到left，這樣的話每一次分區(qū)間也是從最左側開始，會造成遞歸深度過深，可能造成棧溢出。
優(yōu)化點
在選擇樞軸（pivot）時，使用三數取中方法，即選擇數組的左端點、右端點和中點三個元素中的中間值作為樞軸。這一策略主要有以下優(yōu)化點：
- 減少極端情況的概率： 傳統(tǒng)的快速排序如果總是選擇最左或最右的元素作為樞軸，當數組已經接近有序時，可能導致最壞情況下的時間復雜度退化為 O(n2) O(n^2) O(n2)。三數取中減少了這種情況發(fā)生的概率，因為它避免了極端的最小或最大元素作為樞軸。
- 更均勻的劃分： 通過選擇中間值，三數取中方法傾向于產生更均勻的劃分，進而減少遞歸深度，保持算法的時間復雜度在 O(nlog?n) O(n \log n) O(nlogn) 范圍內。
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[right] > a[left])
{
return right;
}
else
{
return left;
}
}
else // a[midi]< a[left]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
優(yōu)化后整體代碼為：
void GetMidQuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
// 左邊找大
// a[end] >= a[keyi] 防止兩個位置相同時一直交換，陷入無限循環(huán)
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 右邊找小
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
/*if (begin < end)
{
Swap(&a[begin], &a[end]);
}*/
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
// 現在的begin位置是之前的keyi位置的數據，所以更新
keyi = begin;
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
小區(qū)間優(yōu)化
原因
小區(qū)間優(yōu)化的原因在于，雖然快速排序平均情況下是高效的，但在處理非常小的數組時，插入排序的常數因子更低，且其性能可能優(yōu)于快速排序。通過將小區(qū)間交給插入排序處理，減少了快速排序的遞歸調用次數和開銷，同時利用插入排序的低開銷特性提升了整體性能。
優(yōu)化點
在處理小區(qū)間（例如長度小于10的數組片段）時，快速排序使用插入排序代替繼續(xù)遞歸。插入排序在小數組上往往更高效，這是因為：
- 減少遞歸開銷： 遞歸的開銷包括函數調用、棧空間的使用等。當區(qū)間足夠小時，這些開銷可能比排序本身更耗時。插入排序的實現簡單，沒有遞歸開銷。
- 插入排序在小數據量時的效率： 插入排序對于小數據量的排序效率高于其他復雜的排序算法（如快速排序、歸并排序等），特別是在數據接近有序的情況下。
// 當區(qū)間長度小于10時，使用插入排序處理
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
return;
}
優(yōu)化后整體代碼：
void InterCellGetMidQuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
// 小區(qū)間優(yōu)化
// right - left + 1為總個數：比如下標十個數的數組下標為 9 - 0，所以要 + 1
if ((right - left + 1) < 10)
{
// 加 left 為了在遞歸分區(qū)間后保持區(qū)間邊界
InsertSort(a + left, right - left + 1);
}
else
{
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
// 左邊找大
// a[end] >= a[keyi] 防止兩個位置相同時一直交換，陷入無限循環(huán)
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 右邊找小
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
/*if (begin < end)
{
Swap(&a[begin], &a[end]);
}*/
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
// 現在的begin位置是之前的keyi位置的數據，所以更新
keyi = begin;
InterCellGetMidQuickSort(a, left, keyi - 1);
InterCellGetMidQuickSort(a, keyi + 1, right);
}
}
遞歸快速排序的完整優(yōu)化實現代碼
void InterCellGetMidQuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
// 小區(qū)間優(yōu)化
// right - left + 1為總個數：比如下標十個數的數組下標為 9 - 0，所以要 + 1
if ((right - left + 1) < 10)
{
// 加 left 為了在遞歸分區(qū)間后保持區(qū)間邊界
InsertSort(a + left, right - left + 1);
}
else
{
// 三數取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
// 左邊找大
// a[end] >= a[keyi] 防止兩個位置相同時一直交換，陷入無限循環(huán)
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 右邊找小
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
/*if (begin < end)
{
Swap(&a[begin], &a[end]);
}*/
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
// 現在的begin位置是之前的keyi位置的數據，所以更新
keyi = begin;
InterCellGetMidQuickSort(a, left, keyi - 1);
InterCellGetMidQuickSort(a, keyi + 1, right);
}
}
非遞歸實現快速排序（棧、DFS）
非遞歸實現快速排序的核心思想是使用棧來模擬遞歸調用的行為。通過顯式地管理棧，可以避免系統(tǒng)棧溢出的問題，同時對棧的管理更加清晰明確。
void QuickSortNonR(int* a, int left, int right)
{
stack<int> st;
st.push(right);
st.push(left);
while (!st.empty())
{
int begin = st.top();
st.pop();
int end = st.top();
st.pop();
// 執(zhí)行快排的單趟邏輯，不遞歸
int keyi = PartQuickSort(a, begin, end);
// 現將后面的區(qū)間入棧
// keyi + 1 : end
if (keyi + 1 < end)
{
st.push(end);
st.push(keyi + 1);
}
if (keyi - 1 > begin)
{
st.push(keyi - 1);
st.push(begin);
}
}
}
代碼過程理解
- 初始化階段:
- 首先，將待排序數組的右邊界
right壓入棧st，然后將左邊界left壓入棧。此時，棧中的內容是[right, left]。
- 第一輪循環(huán):
- 從棧中先彈出
begin（棧頂元素），然后彈出end，代表當前需要處理的子數組的左右邊界。 - 對
a[begin]到a[end]這部分數組執(zhí)行一次快速排序的劃分操作，找到樞軸的位置keyi。 - 根據
keyi的位置，將右子數組（keyi + 1到end）的邊界先后壓入棧，再將左子數組（begin到keyi - 1）的邊界先后壓入棧。注意，每次先壓入區(qū)間的右邊界，再壓入左邊界，這樣在后續(xù)出棧時能夠先處理左子數組。
- 從棧中先彈出
- 第二輪循環(huán)及之后:
- 從棧中再依次彈出
begin和end，處理下一個子數組。 - 執(zhí)行一次劃分操作，確定新的樞軸位置
keyi。 - 同樣，根據
keyi的位置，將新的子數組區(qū)間的邊界按順序壓入棧。
- 從棧中再依次彈出
- 不斷重復:
- 反復從棧中彈出左右邊界，進行子數組的劃分和壓棧操作，直到棧為空。每次棧中壓入的是還未排序的子數組邊界，而從棧中彈出時則是準備進行排序操作的邊界。
- 結束:
- 棧為空時，表示所有子數組均已被排序，整個數組也因此被完全排序。
執(zhí)行的是非遞歸，但是邏輯還是遞歸的邏輯，還是用DFS進行遍歷排序
[0,9]
/ \
[0,4] [5,9]
/ \ / \
[0,2] [3,4] [5,6] [7,9]
/ \ | | \ / \
[0,1] [2,2] [3,4] [5,5] [6,6] [7,8] [9,9]
實例演示
假設初始數組為 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]，初始左右邊界為 left = 0 和 right = 9。棧的初始狀態(tài)是 [9, 0]。
- 第一輪:
- 出棧：
begin = 0,end = 9- 執(zhí)行劃分，假設
keyi = 5- 壓入：
[9, 6, 4, 0]- 第二輪:
- 出棧：
begin = 0,end = 4- 執(zhí)行劃分，假設
keyi = 1- 壓入：
[9, 6, 4, 2]- 第三輪:
- 出棧：
begin = 2,end = 4- 執(zhí)行劃分，假設
keyi = 3- 壓入：
[9, 6, 4, 4]- 第四輪:
- 出棧：
begin = 6,end = 9- 執(zhí)行劃分，假設
keyi = 7- 壓入：
[9, 8, 6, 6]- 第五輪:
- 出棧：
begin = 8,end = 9- 執(zhí)行劃分，假設
keyi = 9- 不再壓入新的邊界，因為子數組已經排序完成
如此循環(huán)，直到棧為空。最終，整個數組被正確排序。
這個過程通過棧結構有效地管理了需要排序的子數組區(qū)間，避免了遞歸帶來的深度問題。每一輪循環(huán)中，都會先處理左邊子數組，這保證了遍歷的順序和處理的深度都受到控制。
歸并排序
歸并排序（Merge Sort）是一種基于分治法（Divide and Conquer）的排序算法，其核心思想是將一個數組分成兩個子數組，對每個子數組分別排序，然后將兩個有序子數組合并成一個有序數組。歸并排序具有穩(wěn)定性和較好的時間復雜度，通常為 O(n log n)。
歸并排序的原理
- 分治法思想: 歸并排序遵循分治法的思想，將問題分解為更小的子問題來解決，然后將子問題的結果合并，以得到最終結果。具體而言：
- 分：將數組從中間劃分為兩個子數組，分別對這兩個子數組進行排序。
- 治：將兩個已排序的子數組合并成一個有序數組。
- 遞歸過程: 歸并排序通過遞歸實現，遞歸地將數組不斷劃分，直到每個子數組的長度為1，此時子數組本身就是有序的。然后，合并這些有序的子數組。
歸并排序過程解析
劃分階段（Divide）
從中間將數組劃分成兩個子數組，分別對兩個子數組進行同樣的操作。這一步通過計算中間位置 mid 來實現：
mid = (begin + end) / 2
繼續(xù)遞歸地對兩個子數組進行同樣的劃分，直到每個子數組只包含一個元素（即 begin >= end）。在這種情況下，數組本身已經是有序的。
合并階段（Conquer）
當子數組被劃分到只包含一個元素時，開始將這些子數組兩兩合并。合并時，通過比較兩個子數組的首元素，將較小的元素放入臨時數組（或直接放入原數組的適當位置），直到所有元素都被合并。
具體合并步驟如下：
- 初始化兩個指針分別指向兩個子數組的起始位置。
- 比較兩個指針指向的元素，將較小的元素拷貝到臨時數組，并移動相應的指針。
- 重復上述步驟，直到一個子數組的所有元素都被拷貝到臨時數組。
- 將另一個子數組剩余的所有元素依次拷貝到臨時數組。
遞歸回溯
隨著遞歸函數的回溯，每次合并兩個子數組，并在回溯結束時，將臨時數組的內容復制回原數組對應的位置，使整個數組逐漸變?yōu)橛行颉?/p>
歸并排序的特性
- 穩(wěn)定性: 歸并排序是一種穩(wěn)定的排序算法，即相同元素的相對順序在排序后保持不變。
- 時間復雜度: 歸并排序在最壞、最好和平均情況下的時間復雜度均為
O(n log n)。這是因為無論如何分，數組總會分為log n層，而每層的合并過程需要O(n)的時間。- 空間復雜度: 歸并排序需要額外的空間來存儲合并過程中的臨時數組，因此空間復雜度為
O(n)。
歸并排序的代碼實現
代碼
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
// 如果[begin, mid][mid+1, end]有序就可以進行歸并了
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
// 歸并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
代碼實現再解析
遞歸劃分
終止條件: 當 begin 大于等于 end 時，子數組的元素個數小于或等于 1，此時無需再分割，直接返回。
if (begin >= end)
return;
劃分數組: 將當前數組的范圍 [begin, end] 分為兩個子數組 [begin, mid] 和 [mid+1, end]，其中 mid 是中間位置。
int mid = (begin + end) / 2;
遞歸排序子數組: 先對左子數組 [begin, mid] 進行排序，再對右子數組 [mid + 1, end] 進行排序。這里遞歸調用 _MergeSort，將問題不斷分解，直到滿足終止條件。
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
合并有序數組
在對兩個子數組 [begin, mid] 和 [mid + 1, end] 排序后，它們分別是有序的。接下來將它們合并成一個有序的數組。
初始化指針:
begin1和end1表示左子數組的范圍。begin2和end2表示右子數組的范圍。i用于指向臨時數組tmp中當前存放位置。
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
合并過程:
比較 a[begin1] 和 a[begin2] 的大小，將較小的元素放入 tmp[i] 中，并移動相應的指針。重復這一過程，直到某一子數組的元素全部放入 tmp 中。
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
處理剩余元素:
- 如果左子數組還有未放入
tmp的元素，則將它們依次放入tmp中。- 同樣地，如果右子數組還有未放入
tmp的元素，則將它們依次放入tmp中。
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
將 **tmp** 中的元素拷貝回原數組:
- 在完成合并后，將
tmp中的元素拷貝回原數組a中的對應位置，保證原數組a中的[begin, end]范圍內的元素有序。
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
總結
歸并排序通過遞歸地將數組分成更小的子數組，然后再合并這些有序子數組來完成排序。它的分治思想和穩(wěn)定性使其在處理大規(guī)模數據時表現良好（ 特別是對于鏈表排序或外部排序“數據存儲在外部存儲器中，如磁盤”的情況 ），但由于需要額外的存儲空間（臨時數組 tmp），在空間效率上可能不如原地排序算法（如快速排序）。
計數排序
計數排序是一種 非比較排序算法，它不同于基于比較的排序算法（如快速排序、歸并排序等），其時間復雜度受限于輸入數據的最大值和最小值之間的范圍，而不是數據本身的數量級。計數排序的核心思想是 利用數組元素的值直接作為索引 來存儲數據，從而避免了元素之間的比較。
代碼實現
// 時間復雜度:O(N+range)
// 只適合整數/適合范圍集中
// 空間范圍度：O(range)
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
//printf("%d\n", range);
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc fail");
return;
}
// 統(tǒng)計次數
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
// 排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
}
算法實現過程及原理
算法的步驟包括找出數組中的最大值和最小值，統(tǒng)計各個元素的頻率，然后根據頻率重新排列數組。
找到最小值和最大值
計數排序首先確定數組中元素的范圍（即最大值和最小值之間的差）。這一步的目的是為了明確輔助數組（即計數數組）的大小。如果范圍過大，計數數組的大小也會很大，導致空間浪費。因此，計數排序適用于數據范圍相對集中的情況。
創(chuàng)建并初始化計數數組
計數數組 count 的大小為 range = max - min + 1。數組的每個元素初始值為0，表示對應元素還未出現。
統(tǒng)計元素出現的次數
遍歷待排序的數組 a，對于每個元素 a[i]，在計數數組 count 中對應位置 count[a[i] - min] 的值加1。這里的 a[i] - min 計算方式將數組的值映射到計數數組的索引范圍 [0, range-1]。這樣，計數數組的每個索引位置記錄了對應元素在數組中出現的次數。
計算元素的累積計數
通過計算計數數組的累積和來確定每個元素在排序后數組中的位置。累積計數實際上表示的是比當前元素值小的元素總個數加上當前元素出現的次數，這樣我們就能直接得到元素排序后在最終數組中的位置。
根據計數排序重構輸出數組
根據累積計數反向遍歷原數組，將每個元素放到輸出數組的正確位置。需要注意的是，這一步必須從原數組的末尾開始向前遍歷，原因是為了保持排序的穩(wěn)定性（即相同元素在排序后的位置相對不變）。
將排序結果拷貝回原數組
將排序好的元素從輸出數組復制回原數組 a 中。
釋放輔助空間
在算法結束時，釋放為計數數組分配的空間。這是為了防止內存泄漏。
算法的時間和空間復雜度
- 時間復雜度：
計數排序的時間復雜度為 O(n+range)O(n + \text{range})O(n+range)，其中n是待排序數組的元素數量，range是元素的取值范圍（即最大值與最小值之差加1）。這是因為計數排序在統(tǒng)計元素出現次數和重新排列元素時各遍歷了兩次數組a和count。 - 空間復雜度：
計數排序的空間復雜度為 O(range)O(\text{range})O(range)。主要是因為需要額外分配一個計數數組count來存儲每個元素的出現次數，大小為range。
計數排序的局限性
- 數據范圍問題：如果輸入數據的范圍
range遠大于元素的數量n，計數排序的空間復雜度將大大增加，甚至超出實際的需求。這會導致內存的浪費。 - 適用場景：由于計數排序依賴于數據范圍的大小，它更適用于數據范圍集中且分布較均勻的整數集合。不適合范圍特別大或者小數的數據集。
- 穩(wěn)定性：雖然計數排序本身是穩(wěn)定的，但這一點依賴于算法的具體實現方式，尤其是在重新排列元素時必須保證同值元素的相對順序不變。
本文來自博客園，作者：DevKevin，轉載請注明原文鏈接：http://www.rzrgm.cn/kevinbee/p/18678236
浙公網安備 33010602011771號