排序 | 冒泡 插入 希爾 選擇 堆 快排 歸并 非遞歸 計(jì)數(shù) 基數(shù) 排序
前言：
排序算法是一種將一組數(shù)據(jù)按照特定順序排列的算法。數(shù)據(jù)結(jié)構(gòu)排序算法的選擇取決于數(shù)據(jù)的特征、規(guī)模和性能需求。
接下來我們就要實(shí)現(xiàn)排序~~
我們需要實(shí)現(xiàn)的一些功能：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
// 打印
void Print_a(int* a, int sz);
// 交換
void Swap(int* p1, int* p2);
// 插入排序
void InsertSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n);
// 希爾排序
void ShellSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 選擇排序
void SelectSort(int* a, int n);
// ------------------------------------------------------
// 快速排序hoare版本
int PartSort1(int* a, int begin, int end);
// 快速排序挖坑法
int PartSort2(int* a, int begin, int end);
// 快速排序前后指針法
int PartSort3(int* a, int begin, int end);
// 排序函數(shù)
void QuickSort(int* a, int begin, int end);
//------------------------------------------------------
// 快速排序 非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a, int begin, int end);
// 歸并排序遞歸實(shí)現(xiàn)
void MergeSort(int* a, int n);
// 歸并排序非遞歸實(shí)現(xiàn)
void MergeSortNonR(int* a, int n);
// 非比較排序
void CountSort(int* a, int n);
冒泡排序
- 冒泡排序是一種基本的排序算法，其核心思想是通過多次交換相鄰元素的位置，使得每一輪循環(huán)都將最大（或最?。┑脑匾苿?dòng)到序列的最后。這個(gè)過程就像氣泡逐漸上升到表面一樣，因而得名"冒泡排序"。
代碼實(shí)現(xiàn)：
void bubbleSort(int* a,int n)
{
for (int i = 0; i < n-1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
優(yōu)點(diǎn)：
- 簡(jiǎn)單易懂： 冒泡排序的思想非常簡(jiǎn)單，容易理解和實(shí)現(xiàn)，適合初學(xué)者學(xué)習(xí)排序算法的基本概念。
- 原地排序： 冒泡排序是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)，只需要一個(gè)常數(shù)級(jí)的輔助空間。
- 穩(wěn)定性： 冒泡排序是一種穩(wěn)定的排序算法，相等元素的相對(duì)位置不會(huì)發(fā)生變化。
缺點(diǎn)：
- 效率低： 冒泡排序的平均時(shí)間復(fù)雜度為O(n^2)，在處理大規(guī)模數(shù)據(jù)時(shí)性能較差，比較和交換的操作太過頻繁。
- 不適合大規(guī)模數(shù)據(jù)： 冒泡排序的性能不如一些更高效的排序算法，如快速排序、歸并排序等，特別是在數(shù)據(jù)規(guī)模較大的情況下。
- 對(duì)基本有序的序列效率低下： 在實(shí)際應(yīng)用中，如果序列已經(jīng)基本有序，冒泡排序仍然需要進(jìn)行多次比較和交換，效率不高。
插入排序
- 插入排序是一種簡(jiǎn)單直觀的排序算法，其核心思想是將一個(gè)元素插入到已經(jīng)排好序的數(shù)組（或子數(shù)組）中的合適位置，以達(dá)到整體有序的效果。插入排序的工作方式類似于整理撲克牌的過程：手里的牌是已經(jīng)有序的部分，新摸到的牌則需要插入到適當(dāng)?shù)奈恢?，保持有序性?/li>
代碼實(shí)現(xiàn)：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
// 記錄每次i的位置
int end = i;
// 將i+1的位置保存
int tmp = a[end + 1];
// 一次排序
while (end >= 0)
{
// 如果后面的數(shù)字小于前面的那一個(gè)就進(jìn)行往后覆蓋，
// 然后end--，繼續(xù)排序
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
// 如果大于或者等于了就跳出
break;
}
}
// 因?yàn)?-end了，所以就要在end+1的位置放剛剛保存的值tmp
a[end + 1] = tmp;
}
}
優(yōu)點(diǎn)：
- 簡(jiǎn)單易理解： 插入排序的實(shí)現(xiàn)非常簡(jiǎn)單，易于理解和實(shí)現(xiàn)，適用于小規(guī)模數(shù)據(jù)或部分有序的數(shù)據(jù)。
- 穩(wěn)定性： 插入排序是一種穩(wěn)定的排序算法，相等元素的相對(duì)位置不會(huì)發(fā)生變化。
- 適應(yīng)性好： 如果數(shù)據(jù)已經(jīng)基本有序，插入排序的性能會(huì)比較好，因?yàn)榇蟛糠衷囟家呀?jīng)在正確的位置上，只需少量的比較和移動(dòng)。
- 原地排序： 插入排序是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)。
缺點(diǎn)：
- 效率低： 插入排序的平均時(shí)間復(fù)雜度為O(n^2)，在數(shù)據(jù)規(guī)模較大時(shí)，性能不如一些更高效的排序算法，如快速排序、歸并排序等。
- 對(duì)大規(guī)模數(shù)據(jù)排序效率低下： 插入排序在處理大規(guī)模數(shù)據(jù)時(shí)性能較差，因?yàn)樗枰罅康谋容^和移動(dòng)操作。
- 不適合鏈表結(jié)構(gòu)： 插入排序需要頻繁地移動(dòng)元素，對(duì)于鏈表結(jié)構(gòu)來說，由于不支持隨機(jī)訪問，插入排序效率較低。
希爾排序
- 希爾排序（Shell Sort）是一種插入排序的改進(jìn)版本，也稱為縮小增量排序。它通過比較相距一定間隔的元素，逐步減小這個(gè)間隔，直到間隔為1時(shí)完成最后一輪排序。希爾排序的核心思想是先使數(shù)組中任意間隔為h的元素有序，然后逐步減小h，最終使整個(gè)數(shù)組有序。
代碼實(shí)現(xiàn)：
void ShellSort(int* a, int n)
{
int gap = n;
// gap > 1時(shí)是預(yù)排序，目的讓他接近有序
// gap == 1是直接插入排序，目的是讓他有序
while (gap > 1)
{
// gap = gap / 2; // log 2 N
gap = gap / 3 + 1; // log 3 N
//每次排gap次
for (int j = 0; j < n - gap; j++)
{
//插入排序
int end = j;
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;
}
}
}
優(yōu)點(diǎn)：
- 相對(duì)于插入排序的改進(jìn)： 希爾排序是插入排序的改進(jìn)版本，通過引入間隔（gap）的概念，減少了數(shù)據(jù)的搬移次數(shù)，提高了效率。
- 適用于中等規(guī)模數(shù)據(jù)： 希爾排序相對(duì)于一些簡(jiǎn)單的排序算法，對(duì)中等規(guī)模的數(shù)據(jù)表現(xiàn)較好，比如對(duì)于幾千甚至幾萬個(gè)元素的排序。
- 不穩(wěn)定性： 相比較于一些穩(wěn)定排序算法（如歸并排序、插入排序），希爾排序的不穩(wěn)定性可能在某些情況下是一個(gè)優(yōu)勢(shì)，特別是在排序過程中需要對(duì)元素進(jìn)行位置交換的場(chǎng)景。
缺點(diǎn)：
- 不適用于大規(guī)模數(shù)據(jù)： 希爾排序的性能相對(duì)較好，但在處理非常大規(guī)模數(shù)據(jù)時(shí)，效率可能不如一些更為高級(jí)的排序算法，比如快速排序、歸并排序等。
- 不穩(wěn)定性： 盡管不穩(wěn)定性在某些情況下可以是優(yōu)勢(shì)，但在某些應(yīng)用場(chǎng)景下，需要保持相等元素的相對(duì)位置不變，這時(shí)候希爾排序的不穩(wěn)定性可能成為一個(gè)缺點(diǎn)。
選擇排序
- 選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法，其基本思想是通過不斷選擇未排序序列中的最?。ɑ蜃畲螅┰?，將其與未排序序列的第一個(gè)元素交換，從而逐步構(gòu)建有序序列。
代碼實(shí)現(xiàn)：
// 選擇排序
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
// 兩頭找
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
// 如果i的位置比mini小就更新一下
if (a[i] < a[mini])
{
mini = i;
}
//如果i的位置比maxi大就更新一下
if (a[i] > a[maxi])
{
maxi = i;
}
}
// 走到這里就說明小的要和左邊交換一下
Swap(&a[mini], &a[begin]);
// 注意：這里Eugene左邊的和maxi相等了要更新一下maxi
if (begin == maxi)
{
maxi = mini;
}
// 然后交換maxi和end
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
優(yōu)點(diǎn)：
- 簡(jiǎn)單易理解： 選擇排序的實(shí)現(xiàn)非常簡(jiǎn)單，易于理解和實(shí)現(xiàn)，適合初學(xué)者學(xué)習(xí)排序算法的基本概念。
- 原地排序： 選擇排序是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)，只需要一個(gè)常數(shù)級(jí)的輔助空間。
- 不穩(wěn)定性： 選擇排序是一種不穩(wěn)定的排序算法，相等元素的相對(duì)位置可能發(fā)生變化，但在某些情況下，不穩(wěn)定性可能是一個(gè)優(yōu)勢(shì)。
缺點(diǎn)：
- 效率低： 選擇排序的平均時(shí)間復(fù)雜度為O(n^2)，在處理大規(guī)模數(shù)據(jù)時(shí)性能較差，由于每次只能確定一個(gè)元素的位置，比較和交換的操作過于頻繁。
- 對(duì)基本有序的序列效率低下： 在實(shí)際應(yīng)用中，如果序列已經(jīng)基本有序，選擇排序仍然需要進(jìn)行大量的比較和交換，效率不高。
- 不適合大規(guī)模數(shù)據(jù)： 選擇排序的性能不如一些更高效的排序算法，如快速排序、歸并排序等，特別是在數(shù)據(jù)規(guī)模較大的情況下。
堆排序
-
堆排序是一種基于二叉堆數(shù)據(jù)結(jié)構(gòu)的排序算法。它利用了堆的性質(zhì)來進(jìn)行排序，其中堆分為最大堆和最小堆兩種類型。在最大堆中，父節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值；在最小堆中，父節(jié)點(diǎn)的值小于或等于其子節(jié)點(diǎn)的值。
-
這里在堆排序章節(jié)已經(jīng)講過了，這里就不細(xì)講了~~
代碼實(shí)現(xiàn)：
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
++child;
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDwon(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
--end;
}
}
優(yōu)點(diǎn)：
- 穩(wěn)定性： 堆排序是一種不穩(wěn)定的排序算法，因?yàn)樵跇?gòu)建初始堆和進(jìn)行堆調(diào)整的過程中可能破壞相同元素的相對(duì)順序。然而，如果對(duì)于相同的元素，可以使用索引來保持其相對(duì)順序，就可以避免這個(gè)問題。
- 原地排序： 堆排序是一種原地排序算法，不需要額外的存儲(chǔ)空間來存儲(chǔ)待排序的數(shù)據(jù)，只需要常數(shù)級(jí)別的輔助空間。
- 時(shí)間復(fù)雜度： 堆排序的平均、最好和最壞情況下的時(shí)間復(fù)雜度都是 O(n log n)，其中 n 是待排序元素的數(shù)量。這使得堆排序在大數(shù)據(jù)集上表現(xiàn)良好。
缺點(diǎn)：
- 非自適應(yīng)性： 堆排序的時(shí)間復(fù)雜度在各種情況下都是 O(n log n)，無論輸入數(shù)據(jù)的初始順序如何。因此，它對(duì)于部分有序的數(shù)據(jù)或者小規(guī)模數(shù)據(jù)集的排序效率可能不如一些自適應(yīng)性較強(qiáng)的算法。
- 不穩(wěn)定： 在排序過程中，堆排序可能破壞相同元素的相對(duì)順序，因此是一種不穩(wěn)定的排序算法。如果對(duì)穩(wěn)定性有要求，可能需要考慮其他算法。
- 不適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 堆排序通常需要對(duì)數(shù)組進(jìn)行直接訪問，而不適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因此，如果數(shù)據(jù)結(jié)構(gòu)采用鏈表形式存儲(chǔ)，需要將其轉(zhuǎn)換為數(shù)組再進(jìn)行排序，這可能引入額外的開銷。
快速排序–交換排序
三數(shù)取中
int GetMidi(int* a, int left, int right)
{
//int midi = (begin + end) / 2;
int mid = (left + right) >> 1;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
return mid;
else if (a[left] > a[right])
return left;
else
return right;
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
return mid;
else if (a[left] < a[right])
return left;
else
return right;
}
}
快速排序hoare版本
- 快速排序是一種常用的排序算法，Hoare版本是其中一種實(shí)現(xiàn)方式，由Tony Hoare提出。
代碼實(shí)現(xiàn)：
int PartSort1(int* a, int begin, int end)
{
// 三數(shù)取中
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
// 要在最左邊開始
int left = begin, right = end;
int keyi = begin;
while (left < right)
{
// 右邊找小
while (left < right && a[right] >= a[keyi])
{
--right;
}
// 左邊找大
while (left < right && a[left] <= a[keyi])
{
++left;
}
// 找到了，就交換
Swap(&a[left], &a[right]);
}
// 交換的左邊的和keyi，然后更新一下keyi
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
// 小區(qū)間
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
優(yōu)點(diǎn)：
- 原地排序： 快速排序是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)，只需要一個(gè)常數(shù)級(jí)的輔助空間。
- 平均情況下具有較好的性能： 在平均情況下，快速排序的時(shí)間復(fù)雜度為O(n log n)，這使得它在實(shí)踐中具有較好的性能。
- 適用于大規(guī)模數(shù)據(jù)： 快速排序在處理大規(guī)模數(shù)據(jù)時(shí)通常表現(xiàn)良好，尤其是相對(duì)于一些平均時(shí)間復(fù)雜度較高的排序算法而言。
- 對(duì)基本有序的數(shù)據(jù)排序效果好： 在一些情況下，快速排序?qū)居行虻臄?shù)據(jù)排序效果較好。
缺點(diǎn)：
- 不穩(wěn)定性： 快速排序是一種不穩(wěn)定的排序算法，相等元素的相對(duì)位置可能發(fā)生變化，如果需要穩(wěn)定性，可能需要額外的處理。
- 對(duì)于極端情況的性能： 在最壞情況下，即已經(jīng)有序的序列，快速排序的時(shí)間復(fù)雜度為O(n^2)，這時(shí)性能可能較差。為了避免這種情況，通常會(huì)使用一些優(yōu)化策略，比如隨機(jī)化選擇樞軸。
- 對(duì)于小規(guī)模數(shù)據(jù)性能較差： 在小規(guī)模數(shù)據(jù)的排序中，快速排序的遞歸調(diào)用會(huì)增加額外的開銷，性能可能不如一些簡(jiǎn)單的排序算法，如插入排序。
快速排序挖坑法
- 快速排序的挖坑法（也稱為L(zhǎng)omuto分區(qū)方案）是快速排序的一種實(shí)現(xiàn)方式。在挖坑法中，選擇一個(gè)基準(zhǔn)元素，通過不斷交換元素將數(shù)組分成兩個(gè)部分，左邊的部分都小于基準(zhǔn)元素，右邊的部分都大于基準(zhǔn)元素。接著，對(duì)左右兩個(gè)部分分別遞歸進(jìn)行同樣的操作。
代碼實(shí)現(xiàn)：
int PartSort2(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int holei = begin;
while (begin < end)
{
// 右邊找小
while (begin < end && a[end] >= key)
{
--end;
}
a[holei] = a[end];
holei = end;
// 左邊找大
while (begin < end && a[begin] <= key)
{
++begin;
}
a[holei] = a[begin];
holei = begin;
}
a[holei] = key;
return holei;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
// 小區(qū)間
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort2(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
優(yōu)點(diǎn)：
- 原地排序： 挖坑法是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)，只需要一個(gè)常數(shù)級(jí)的輔助空間。
- 簡(jiǎn)單直觀： 挖坑法實(shí)現(xiàn)相對(duì)較簡(jiǎn)單，容易理解和實(shí)現(xiàn)，適用于教學(xué)和學(xué)習(xí)排序算法。
缺點(diǎn)：
- 不穩(wěn)定性： 挖坑法是一種不穩(wěn)定的排序算法，相等元素的相對(duì)位置可能發(fā)生變化，如果需要穩(wěn)定性，可能需要額外的處理。
- 最壞情況下的性能： 在最壞情況下，即已經(jīng)有序的序列，挖坑法的性能可能較差。這時(shí)的時(shí)間復(fù)雜度為O(n^2)，因?yàn)槊看畏謪^(qū)只能使序列中的一個(gè)元素有序。
- 對(duì)于小規(guī)模數(shù)據(jù)性能較差： 在小規(guī)模數(shù)據(jù)的排序中，挖坑法的遞歸調(diào)用會(huì)增加額外的開銷，性能可能不如一些簡(jiǎn)單的排序算法，如插入排序。
快速排序前后指針法
- 快速排序的前后指針法（也稱為Hoare分區(qū)方案）是另一種實(shí)現(xiàn)方式。在這個(gè)方法中，通過兩個(gè)指針從數(shù)組的兩端分別向中間移動(dòng)，交換不符合排序條件的元素，最終將數(shù)組分為兩個(gè)部分，左邊部分小于基準(zhǔn)元素，右邊部分大于基準(zhǔn)元素。
代碼實(shí)現(xiàn)：
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[begin], &a[midi]);
int prev = begin;
int cur = prev + 1;
int keyi = begin;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
// 小區(qū)間
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1);
}
else
{
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
優(yōu)點(diǎn)：
- 原地排序： 前后指針法是一種原地排序算法，不需要額外的空間來存儲(chǔ)臨時(shí)數(shù)據(jù)，只需要一個(gè)常數(shù)級(jí)的輔助空間。
- 相對(duì)較好的性能： 在平均情況下，快速排序的前后指針法具有較好的性能，時(shí)間復(fù)雜度為O(n log n)。
- 不需要額外的空間： 與挖坑法相比，前后指針法在實(shí)際的操作中，不需要額外的元素用于填坑，從而減少了一些操作。
缺點(diǎn)：
- 不穩(wěn)定性： 前后指針法是一種不穩(wěn)定的排序算法，相等元素的相對(duì)位置可能發(fā)生變化，如果需要穩(wěn)定性，可能需要額外的處理。
- 最壞情況下的性能： 在最壞情況下，即已經(jīng)有序的序列，前后指針法的性能可能較差。這時(shí)的時(shí)間復(fù)雜度為O(n^2)，因?yàn)槊看畏謪^(qū)只能使序列中的一個(gè)元素有序。
- 對(duì)于小規(guī)模數(shù)據(jù)性能較差： 在小規(guī)模數(shù)據(jù)的排序中，前后指針法的遞歸調(diào)用會(huì)增加額外的開銷，性能可能不如一些簡(jiǎn)單的排序算法，如插入排序。
快速排序–非遞歸實(shí)現(xiàn)
- 我們這里使用棧來解決這個(gè)問題~~
- 先入棧，然后再進(jìn)行分割
- 注意： 如果是先入右后入左，那么出的時(shí)候就要先出左后出右
- 棧不為空就繼續(xù)，然后分割排左邊和右邊
代碼實(shí)現(xiàn)：
#include"Stack.h"
// 快速排序 非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a, int begin, int end)
{
ST s;
StackInit(&s);
// 先入右后入左
StackPush(&s, end);
StackPush(&s, begin);
while (!StackEmpty(&s))
{
// 先出左后出右
int left = StackTop(&s);
StackPop(&s);
int right = StackTop(&s);
StackPop(&s);
// 排序
int keyi = PartSort3(a, left, right);
// [left keyi-1] keyi [keyi+1 right]
if (left < keyi - 1)
{
StackPush(&s, keyi - 1);
StackPush(&s, left);
}
if (keyi + 1 < right)
{
StackPush(&s, right);
StackPush(&s, keyi + 1);
}
}
StackDestroy(&s);
}
歸并排序
- 歸并排序（Merge Sort）是一種分治算法，它的基本思想是將待排序的數(shù)組分成兩個(gè)相等大小的子數(shù)組，然后分別對(duì)這兩個(gè)子數(shù)組進(jìn)行排序，最后將排序好的子數(shù)組合并成一個(gè)有序的數(shù)組。
代碼實(shí)現(xiàn)：
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;
// 分割 // 這里右移一位相當(dāng)于 /2
int mid = (begin + end) >> 1;
// 遞歸
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
// [begin mid][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++];
}
// 拷貝回原數(shù)組
for (int i = begin; i <= end; ++i)
{
a[i] = tmp[i];
}
//memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin) + 1);
}
// 歸并排序遞歸實(shí)現(xiàn)
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!\n");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
優(yōu)點(diǎn)：
- 穩(wěn)定性： 歸并排序是一種穩(wěn)定的排序算法，即對(duì)于相等的元素，它們?cè)谂判蚝蟮南鄬?duì)位置保持不變。
- 適用于鏈表： 歸并排序?qū)τ阪湵淼确请S機(jī)訪問結(jié)構(gòu)的數(shù)據(jù)也非常有效，因?yàn)樗簧婕半S機(jī)訪問，只涉及指針操作。
- 適用于外部排序： 歸并排序在外部排序（需要對(duì)外部存儲(chǔ)進(jìn)行排序的情況）中表現(xiàn)良好，因?yàn)樗梢院苋菀椎赝ㄟ^合并有序的外部文件來實(shí)現(xiàn)。
- 穩(wěn)定的時(shí)間復(fù)雜度： 歸并排序的時(shí)間復(fù)雜度是穩(wěn)定的，不受輸入數(shù)據(jù)的影響，總是O(n log n)。
缺點(diǎn)：
- 額外空間需求： 歸并排序需要額外的內(nèi)存空間來存儲(chǔ)臨時(shí)數(shù)組，這使得它的空間復(fù)雜度相對(duì)較高，是O(n)。
- 非原地排序： 歸并排序是一種非原地排序算法，即它需要額外的空間來存儲(chǔ)臨時(shí)數(shù)組，而不是在原始數(shù)組上進(jìn)行排序。這對(duì)于內(nèi)存受限的情況可能不太理想。
- 常數(shù)因子較大： 歸并排序的常數(shù)因子較大，因此在實(shí)際應(yīng)用中可能被一些其他排序算法（如快速排序）超越。
歸并排序非遞歸實(shí)現(xiàn)
- 思想和上面的歸并排序差不多~~
代碼實(shí)現(xiàn)：
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1; // 每組數(shù)據(jù)個(gè)數(shù)
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [i, i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 歸并過程中右半?yún)^(qū)間可能就不存在
if (begin2 >= n)
break;
// 歸并過程中右半?yún)^(qū)間算多了, 修正一下
if (end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
// 拷貝回去
for (int j = i; j <= end2; ++j)
{
a[j] = tmp[j];
}
}
gap *= 2;
}
free(tmp);
}
非比較排序【計(jì)數(shù)排序】
- 計(jì)數(shù)排序（Counting Sort）是一種非比較性的整數(shù)排序算法，它通過確定每個(gè)元素在輸出序列中的位置來實(shí)現(xiàn)排序。
代碼實(shí)現(xiàn)：
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail!\n");
return;
}
memset(count, 0, sizeof(int) * range);
//統(tǒng)計(jì)次數(shù)
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count);
}
優(yōu)點(diǎn)：
- 線性時(shí)間復(fù)雜度： 計(jì)數(shù)排序是一種具有線性時(shí)間復(fù)雜度的排序算法，其時(shí)間復(fù)雜度為O(n + k)，其中n是輸入元素的數(shù)量，k是輸入范圍的大小。在輸入范圍較小的情況下，計(jì)數(shù)排序通常比其他O(n log n)的排序算法更快。
- 穩(wěn)定性： 計(jì)數(shù)排序是一種穩(wěn)定的排序算法，即相等元素的相對(duì)順序在排序后仍然保持不變。
- 適用于整數(shù)排序： 計(jì)數(shù)排序適用于整數(shù)排序，尤其是在知道輸入范圍不太大的情況下。它不依賴于比較操作，因此在某些情況下可能比基于比較的排序算法更高效。
缺點(diǎn)：
- 空間復(fù)雜度： 計(jì)數(shù)排序的主要缺點(diǎn)是它需要額外的空間來存儲(chǔ)計(jì)數(shù)數(shù)組。如果輸入范圍很大，可能需要較大的額外空間，這可能導(dǎo)致空間復(fù)雜度較高。
- 僅適用于整數(shù)： 計(jì)數(shù)排序僅適用于整數(shù)排序，因?yàn)樗蕾囉趯⒃赜成涞接?jì)數(shù)數(shù)組的索引。對(duì)于浮點(diǎn)數(shù)或其他數(shù)據(jù)類型，需要進(jìn)行額外的轉(zhuǎn)換。
- 對(duì)輸入范圍的限制： 計(jì)數(shù)排序要求輸入的元素必須在已知范圍內(nèi)，否則需要進(jìn)行范圍的確定和調(diào)整，增加了實(shí)現(xiàn)的復(fù)雜性。
基數(shù)排序
- 基數(shù)排序是一種非比較性的排序算法，它根據(jù)關(guān)鍵字的每一位來排序數(shù)據(jù)。
代碼實(shí)現(xiàn)：
這里就先不實(shí)現(xiàn)，之后會(huì)開一個(gè)新文章來進(jìn)行闡述，并且使用C++來寫~~
優(yōu)點(diǎn)：
- 穩(wěn)定性： 基數(shù)排序是一種穩(wěn)定的排序算法，即相等元素的相對(duì)順序在排序后保持不變。
- 適用范圍廣： 基數(shù)排序?qū)τ跀?shù)據(jù)的分布沒有特殊的要求，適用于各種數(shù)據(jù)類型，包括整數(shù)、字符串等。
- 適用于大量數(shù)據(jù)： 在某些情況下，基數(shù)排序的性能可能比一些常見的比較性排序算法（如快速排序、歸并排序）更好，尤其是當(dāng)數(shù)據(jù)量非常大時(shí)。
- 不受輸入數(shù)據(jù)范圍限制： 基數(shù)排序不受輸入數(shù)據(jù)范圍的限制，可以處理負(fù)數(shù)和小數(shù)。
缺點(diǎn)：
- 空間復(fù)雜度較高： 基數(shù)排序的空間復(fù)雜度取決于數(shù)據(jù)的位數(shù)，如果數(shù)據(jù)位數(shù)很大，可能需要較大的輔助空間來存儲(chǔ)中間結(jié)果。
- 不適用于小范圍數(shù)據(jù)： 當(dāng)數(shù)據(jù)范圍比較小而位數(shù)較大時(shí)，基數(shù)排序可能不是最優(yōu)選擇，因?yàn)樗枰^大的輔助空間。
- 只能處理正整數(shù)或字符串： 基數(shù)排序主要用于整數(shù)或字符串的排序，對(duì)于其他數(shù)據(jù)類型可能需要轉(zhuǎn)換為整數(shù)或字符串形式，增加了額外的開銷。
- 效率受制于位數(shù)： 基數(shù)排序的效率受制于位數(shù)，如果位數(shù)很大，可能需要進(jìn)行多輪排序，導(dǎo)致時(shí)間復(fù)雜度較高。
排序算法復(fù)雜度及穩(wěn)定性分析
文章來源：http://www.zghlxwxcb.cn/news/detail-763062.html
本期內(nèi)容就到這里了，感謝大家的收看，歡迎三連~~文章來源地址http://www.zghlxwxcb.cn/news/detail-763062.html
到了這里，關(guān)于排序 | 冒泡 插入 希爾 選擇 堆 快排 歸并 非遞歸 計(jì)數(shù) 基數(shù) 排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
