深入學(xué)習(xí)C語(yǔ)言中常見的八大排序
排序是非常重要的內(nèi)容，一般來說，我們經(jīng)常用到的也就是十大排序，如圖所示
按照比較類和非比較類又可以分為：
冒泡排序
冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
作為最簡(jiǎn)單的排序算法之一，冒泡排序給我的感覺就像 Abandon 在單詞書里出現(xiàn)的感覺一樣，每次都在第一頁(yè)第一位，所以最熟悉。冒泡排序還有一種優(yōu)化算法，就是立一個(gè) flag，當(dāng)在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序。但這種改進(jìn)對(duì)于提升性能來
1.算法描述
比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
2.動(dòng)圖展示
3.圖解展示
4.代碼實(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]);
}
}
}
}
5.冒泡排序的優(yōu)化
如果我們的冒泡排序比較了一圈之后發(fā)現(xiàn)沒有發(fā)生交換，說明此時(shí)已經(jīng)有序了。我們就可以退出循環(huán)。
void BubbleSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int flag = 1;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
flag = 0;
swap(a[j], a[j + 1]);
}
}
if (flag) {
break;
}
}
}
6.復(fù)雜度分析
時(shí)間復(fù)雜度：O（N^2)
若數(shù)組為倒序，即所有的輪次都必須執(zhí)行完（最壞情況），比較次數(shù)為 n-1 + n-2 +...+ 1 = n(n-1)/2，交換次數(shù)與比較次數(shù)相同，所以時(shí)間復(fù)雜度為O(N^2)。
空間復(fù)雜度:O(1)
穩(wěn)定性：插入排序是穩(wěn)定的排序算法，滿足條件nums[j] > nums[j + 1]才發(fā)生交換，這個(gè)條件可以保證值相等的元素的相對(duì)位置不變
插入排序
插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的。 按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列排為有序的過程，稱為插入排序 。插入排序的代碼實(shí)現(xiàn)雖然沒有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
1.算法描述
將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面）
2.動(dòng)圖展示
3.圖解展示
4.代碼實(shí)現(xiàn)
void Insert(int* a, int n)
{
for (int i = 0; i < n - 1; i++) {
int j = 0;
int tmp = a[i + 1];
for (j = i; j >= 0 && tmp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}
或者也可以這樣寫，這樣寫邏輯更清晰：
void Insert(int* a, int n)
{
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
--end;
}
else {
break;
}
}
a[end + 1] = tmp;
}
}
5.復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n2)
- 空間復(fù)雜度：O(1)，只需要一個(gè)額外空間用于交換
- 穩(wěn)定性：插入排序是穩(wěn)定的排序算法，滿足條件
nums[j] > nums[j + 1]才發(fā)生交換，這個(gè)條件可以保證值相等的元素的相對(duì)位置不變
希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
- 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；
- 但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
1.算法描述
選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；
每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度
2.動(dòng)圖展示
3.圖解展示
或者：
4.代碼實(shí)現(xiàn)
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}
5.復(fù)雜度分析
1、時(shí)間復(fù)雜度：O(N^2)
希爾排序最壞的時(shí)間復(fù)雜度依然為 O ( N 2 )
但其能夠有效改善直接插入排序序列無序且長(zhǎng)度大時(shí)的大長(zhǎng)度數(shù)列移位。希爾排序中對(duì)于增量序列的選擇十分重要，直接影響到希爾排序的性能，本文使用的是希爾增量，還有 Hibbard 增量，時(shí)間復(fù)雜度為 O(N^1.5) 也可以認(rèn)為是O ( N^log N)空間復(fù)雜度：O(1)
未借助其它輔助空間。
穩(wěn)定性分析：
與直接插入排序不同，希爾排序中的分組插入可能導(dǎo)致順序移位。
所以，插入排序是穩(wěn)定的排序算法。
堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
1.算法描述
① 將待排序的序列構(gòu)造成一個(gè)最大堆，此時(shí)序列的最大值為根節(jié)點(diǎn)
② 依次將根節(jié)點(diǎn)與待排序序列的最后一個(gè)元素交換
③ 再維護(hù)從根節(jié)點(diǎn)到該元素的前一個(gè)節(jié)點(diǎn)為最大堆，如此往復(fù)，最終得到一個(gè)遞增序列 先將初始的R[0…n-1]建立成最大堆，此時(shí)是無序堆，而堆頂是最大元素。
再將堆頂R[0]和無序區(qū)的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[0…n-2]和有序區(qū)R[n-1]，且滿足R[0…n-2].keys ≤ R[n-1].key
由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。
直到無序區(qū)只有一個(gè)元素為止。
2.動(dòng)圖展示
3.圖解展示
1.預(yù)備知識(shí)：
堆的結(jié)構(gòu)可以分為大根堆和小根堆，是一個(gè)完全二叉樹，而堆排序是根據(jù)堆的這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序，下面先來看看什么是大根堆和小根堆
2.大根堆和小根堆：
性質(zhì)：每個(gè)結(jié)點(diǎn)的值都大于其左孩子和右孩子結(jié)點(diǎn)的值，稱之為大根堆；每個(gè)結(jié)點(diǎn)的值都小于其左孩子和右孩子結(jié)點(diǎn)的值，稱之為小根堆。如下圖
對(duì)應(yīng)成數(shù)組便是：
4.堆的一些基本性質(zhì)
查找數(shù)組中某個(gè)數(shù)的父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)，比如已知索引為i的數(shù)，那么
1.父結(jié)點(diǎn)索引：(i-1)/2（這里計(jì)算機(jī)中的除以2，省略掉小數(shù)）
2.左孩子索引：2*i+1
3.右孩子索引：2*i+2
所以上面兩個(gè)數(shù)組可以腦補(bǔ)成堆結(jié)構(gòu)，因?yàn)樗麄儩M足堆的定義性質(zhì)：
大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)
小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)
5.堆的構(gòu)造
將無序數(shù)組構(gòu)造成一個(gè)大根堆（升序用大根堆，降序就用小根堆）
假設(shè)存在以下數(shù)組
主要思路：第一次保證0~0位置大根堆結(jié)構(gòu)（廢話），第二次保證0~1位置大根堆結(jié)構(gòu)，第三次保證0~2位置大根堆結(jié)構(gòu)...直到保證0~n-1位置大根堆結(jié)構(gòu)（每次新插入的數(shù)據(jù)都與其父結(jié)點(diǎn)進(jìn)行比較，如果插入的數(shù)比父結(jié)點(diǎn)大，則與父結(jié)點(diǎn)交換，否則一直向上交換，直到小于等于父結(jié)點(diǎn)，或者來到了頂端）
插入6的時(shí)候，6大于他的父結(jié)點(diǎn)3，即arr(1)>arr(0)，則交換；此時(shí)，保證了0~1位置是大根堆結(jié)構(gòu)，如下圖：
插入8的時(shí)候，8大于其父結(jié)點(diǎn)6，即arr(2)>arr(0),則交換；此時(shí)，保證了0~2位置是大根堆結(jié)構(gòu)，如下圖
插入5的時(shí)候，5大于其父結(jié)點(diǎn)3，則交換，交換之后，5又發(fā)現(xiàn)比8小，所以不交換；此時(shí)，保證了0~3位置大根堆結(jié)構(gòu)，如下圖
插入7的時(shí)候，7大于其父結(jié)點(diǎn)5，則交換，交換之后，7又發(fā)現(xiàn)比8小，所以不交換；此時(shí)整個(gè)數(shù)組已經(jīng)是大根堆結(jié)構(gòu)
此時(shí)，我們已經(jīng)得到一個(gè)大根堆，下面將頂端的數(shù)與最后一位數(shù)交換，然后將剩余的數(shù)再構(gòu)造成一個(gè)大根堆
此時(shí)最大數(shù)8已經(jīng)來到末尾，則固定不動(dòng)，后面只需要對(duì)頂端的數(shù)據(jù)進(jìn)行操作即可，拿頂端的數(shù)與其左右孩子較大的數(shù)進(jìn)行比較，如果頂端的數(shù)大于其左右孩子較大的數(shù)，則停止，如果頂端的數(shù)小于其左右孩子較大的數(shù)，則交換，然后繼續(xù)與下面的孩子進(jìn)行比較
下圖中，5的左右孩子中，左孩子7比右孩子6大，則5與7進(jìn)行比較，發(fā)現(xiàn)5<7，則交換；交換后，發(fā)現(xiàn)5已經(jīng)大于他的左孩子，說明剩余的數(shù)已經(jīng)構(gòu)成大根堆，后面就是重復(fù)固定最大值，然后構(gòu)造大根堆
如下圖：頂端數(shù)7與末尾數(shù)3進(jìn)行交換，固定好7，
剩余的數(shù)開始構(gòu)造大根堆 ，然后頂端數(shù)與末尾數(shù)交換，固定最大值再構(gòu)造大根堆，重復(fù)執(zhí)行上面的操作，最終會(huì)得到有序數(shù)組
重點(diǎn)建堆的時(shí)間復(fù)雜度：因?yàn)槎咽峭耆鏄洌鴿M二叉樹也是完全二叉樹，此處為了簡(jiǎn)化使用滿二叉樹來證明(時(shí)間復(fù)雜度本來看的就是近似值，多幾個(gè)節(jié)點(diǎn)不影響最終結(jié)果)：
6.代碼實(shí)現(xiàn)
void AdjustDown(int*a,int root,int n) {
int parent = root;
int child = 2 * parent + 1;//向下調(diào)整算法
while (child < n) {
if (child+1<n&&a[child] < a[child + 1]) {
++child;
}
if (a[child] > a[parent]) {
swap(a[child], a[parent]);
parent = child;
child = 2 * parent + 1;
}
else {
break;
}
}
}
void HeapSort(int* a, int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(a, i, n);
}
int end = n - 1;
while (end>0) {
swap(a[0], a[end]);
AdjustDown(a, 0, end);
end--;
}
}
7.復(fù)雜度分析
時(shí)間復(fù)雜度：O（N*log N)
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
選擇排序
選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。 它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰?，然后放到已排序的序列的末尾?以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零
1.算法描述
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
重復(fù)第二步，直到所有元素均排序完畢
2.動(dòng)圖展示
3.圖解展示
4.代碼實(shí)現(xiàn)
void SelectSort(int* a, int n) {
int left = 0;
int right = n - 1;
int minIndex = left, maxIndex = left;
while (left < right) {
for (int i = left; i <= right; i++) {
if (a[i] < a[minIndex]) {
minIndex = i;
}
if (a[i] > a[maxIndex]) {
maxIndex = i;
}
}
swap(a[left], a[minIndex]);
if (left == maxIndex) {//如果max和left位置重疊，修正一下
maxIndex = minIndex;
}
swap(a[right], a[maxIndex]);
left++;
right--;
}
}
5.復(fù)雜度
時(shí)間復(fù)雜度：O（N^2)
空間復(fù)雜度O（1）
穩(wěn)定性：不穩(wěn)定
快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦牭竭@個(gè)名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好，可是這是為什么呢，我也不知道。好在我的強(qiáng)迫癥又犯了，查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競(jìng)賽》上找到了滿意的答案：快速排序的最壞運(yùn)行情況是 O(n2)，比如說順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn)，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。
1.算法簡(jiǎn)介
從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）;
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；
2.動(dòng)圖展示
3.圖解展示
- 挖坑法：
挖坑法：
1、定義begin和end分別指向數(shù)據(jù)的第一個(gè)元素和最后一個(gè)元素，找一個(gè)基準(zhǔn)值key（一般三數(shù)取中法）,置array[begin]的位置上的值為基準(zhǔn)值，并為第一個(gè)坑。
2、end從后往前走，找比key小的值，找到之后，將array[end]賦值給array[begin]，填充begin位置的坑，此時(shí)end位置為一個(gè)新的
3、begin從前往后走，找比key大的值，找到之后，將array[begin]賦值給array[end]，填充end位置的坑，此時(shí)begin位置為一個(gè)坑
4、此類方法依次填坑，當(dāng)begin和end相遇，則循環(huán)結(jié)束，將key的值填最后一個(gè)坑。
上面這種種單趟排序的方法我們稱為挖坑法
4.代碼實(shí)現(xiàn)
int partition2(int* a, int left, int right) {
int mid = GetMindIndex(a, left, right);//三數(shù)取中
int key = a[left];
swap(key, a[mid]);
while (left < right) {
while (left < right && a[right] >= key) {
--right;
}
a[left] = a[right];
while (left < right && a[left] <= key) {
++left;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
三數(shù)取中代碼：
int GetMindIndex(int* a, int left, int right) {
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 {
if (a[mid] > a[right]) {
return mid;
}
else if (a[left] < a[right]) {
return left;
}
else {
return right;
}
}
}
總代碼：
int GetMindIndex(int* a, int left, int right) {//三數(shù)取中
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 {
if (a[mid] > a[right]) {
return mid;
}
else if (a[left] < a[right]) {
return left;
}
else {
return right;
}
}
}
、
int partition2(int* a, int left, int right) {//挖坑法
int mid = GetMindIndex(a, left, right);
int key = a[left];
swap(key, a[mid]);
while (left < right) {
while (left < right && a[right] >= key) {
--right;
}
a[left] = a[right];
while (left < right && a[left] <= key) {
++left;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
void QuickSort(int* a, int left, int right) {//快速排序
if (left >= right)
return;
int mid = partition2(a, left, right);
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
下面我們來看一下前后指針法：
- 前后指針法：
1、選擇一個(gè)基準(zhǔn)值key，定義兩個(gè)指針prev和cur（prev指向pPcur的前一個(gè)位置）
2、當(dāng)cur標(biāo)記的元素比key小時(shí)，prev和cur同時(shí)走，當(dāng)cur標(biāo)記的元素比key大時(shí)，只有cur繼續(xù)向前走（此時(shí)prev停下來），當(dāng)cur走到標(biāo)記的元素比key值小時(shí)，cur停下，prev向前走一步，此時(shí)交換arr[cur]和arr[prev],然后，cur繼續(xù)往前走。
3、當(dāng)cur走出界了，將prev位置的值與key交換。
對(duì)應(yīng)動(dòng)圖：
對(duì)應(yīng)代碼實(shí)現(xiàn)：
int partition3(int* a, int left, int right) {
int cur = left + 1;
int prev = left;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur) {
swap(a[cur], a[prev]);
}
++cur;
}
swap(a[prev], a[key]);
return prev;
}
總代碼：
int GetMindIndex(int* a, int left, int right) {
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 {
if (a[mid] > a[right]) {
return mid;
}
else if (a[left] < a[right]) {
return left;
}
else {
return right;
}
}
}
int partition3(int* a, int left, int right) {
int cur = left + 1;
int prev = left;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur) {
swap(a[cur], a[prev]);
}
++cur;
}
swap(a[prev], a[key]);
return prev;
}
void QuickSort(int* a, int left, int right) {
if (left >= right)
return;
int mid = partition2(a, left, right);
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
- 左右指針法
1、定義兩個(gè)指針begin（指向首元素）和end（指向尾元素），找一個(gè)基準(zhǔn)值key（一般三數(shù)取中法），置于序列的第一個(gè)元素，也就是begin的位置。
2、end從后往前走找比基準(zhǔn)值小的元素（找到后也停下），begin從前往后走找比基準(zhǔn)值key大的元素（找到后停下），
然后，交換arr[begin]和arr[end]，依次循環(huán)操作。
3、當(dāng)begin與end相遇，將array[begin]或array[end]與基準(zhǔn)值交換。
對(duì)應(yīng)圖解：
對(duì)應(yīng)代碼：
int partition(int* a, int start,int end) {
int mid = GetMindIndex(a, start, end);
int key = start;
swap(a[key], a[mid]);
while (start < end){
while (start<end && a[end]>=a[key]) {
--end;
}
while (start < end && a[start] <= a[key]) {
++start;
}
swap(a[start], a[end]);
}
swap(a[key], a[start]);
return start;
}
代碼匯總：
int GetMindIndex(int* a, int left, int right) {//三數(shù)取中
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 {
if (a[mid] > a[right]) {
return mid;
}
else if (a[left] < a[right]) {
return left;
}
else {
return right;
}
}
}
int partition(int* a, int start,int end) {//左右指針法
int mid = GetMindIndex(a, start, end);
int key = start;
swap(a[key], a[mid]);
while (start < end){
while (start<end && a[end]>=a[key]) {
--end;
}
while (start < end && a[start] <= a[key]) {
++start;
}
swap(a[start], a[end]);
}
swap(a[key], a[start]);
return start;
}
void QuickSort(int* a, int left, int right) {
if (left >= right)
return;
int mid = partition2(a, left, right);
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
快速排序需要注意的是：
如果選取左邊做key,并且使用的是左右指針法或者是挖坑法那么右邊要先走才能保證結(jié)果的正確性
int partition2(int* a, int left, int right) {//挖坑法
int mid = GetMindIndex(a, left, right);
int key = a[left];
swap(key, a[mid]);
while (left < right) {
while (left < right && a[right] >= key) {//這里一定要加等于否則有些情況會(huì)死循環(huán)
--right;
}
a[left] = a[right];
while (left < right && a[left] <= key) {//這里一定要加等于否則有些情況會(huì)死循環(huán)
++left;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
挖坑法也是一樣的要加等于如果不加等于在某些極端情況下會(huì)死循環(huán)
比如：
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
那么它就會(huì)死循環(huán)?。。。。。。。。?！
- 快速排序非遞歸
在數(shù)據(jù)結(jié)構(gòu)中，即使遞歸能解決的，我們也有必要掌握非遞歸的方法。我們知道，堆空間比棧的空間大得多，當(dāng)我們?cè)跅Ｖ羞f歸調(diào)函數(shù)，會(huì)增加棧的開銷，棧幀會(huì)多。導(dǎo)致棧溢出程序崩潰。而在堆上遞歸調(diào)用函數(shù)，即使大的遞歸調(diào)用也不會(huì)使程序崩潰。這在安全方面就解決了棧溢出的問題。
遞歸就是自上而下，再自下而上。也就滿足了我們數(shù)據(jù)結(jié)構(gòu)中的棧。所以這里我們可以借助棧來實(shí)現(xiàn)非遞歸的快速排序。
對(duì)應(yīng)代碼實(shí)現(xiàn)：
int partition2(int* a, int left, int right) {
int mid = GetMindIndex(a, left, right);
int key = a[left];
swap(key, a[mid]);
while (left < right) {
while (left < right && a[right] >= key) {
--right;
}
a[left] = a[right];
while (left < right && a[left] <= key) {
++left;
}
a[right] = a[left];
}
a[left] = key;
return left;
}
void QuickSortNonR(int* a, int n) {
int right = n - 1;
int left = 0;
stack<int>ans;
ans.push(right);
ans.push(left);
while (!ans.empty()) {
int left = ans.top();
ans.pop();
int right = ans.top();
ans.pop();
int mid = partition(a, left, right);
if (left + 1 < mid) {
ans.push(mid - 1);
ans.push(left);
}
if (mid + 1 < right) {
ans.push(right);
ans.push(mid + 1);
}
}
}
時(shí)間復(fù)雜度
歸并排序：
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：
- 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
- 自下而上的迭代；然而，在 JavaScript 中這種方式不太可行，因?yàn)檫@個(gè)算法的遞歸深度對(duì)它來講太深了。說實(shí)話，我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教。和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
1.算法分析
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；
- 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
- 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
- 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
2.動(dòng)圖展示
3.圖解展示
可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)（也可采用迭代的方式去實(shí)現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。
合并相鄰有序子序列
再來看看治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實(shí)現(xiàn)步驟
對(duì)應(yīng)代碼實(shí)現(xiàn)：
void _MerageSort(int* a, int* tmp , int left, int right) {
if (left >= right)return;
int mid = (left + right) >> 1;
_MerageSort(a,tmp, left, mid);
_MerageSort(a,tmp, mid + 1, right);
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right;
int index = left;
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 i = left; i <= right; i++) {
a[i] = tmp[i];
}
}
void MerageSort(int* a, int n) {
int* tmp = new int[n];
_MerageSort(a, tmp, 0, n - 1);
delete[] tmp;
}
非遞歸：
基本思路：看作是一顆倒過來的滿二叉樹，兩兩成對(duì)
實(shí)現(xiàn)思路
基本思路：
1、在State0初始狀態(tài)時(shí)，兩兩合并，合并用到的算法是“合并有序的數(shù)組 merge sorted array”。即每次合并得到的都是有序的數(shù)組。
2、兩兩合并的規(guī)則是：將兩個(gè)相同序列長(zhǎng)度的序列進(jìn)行合并，合并后的序列長(zhǎng)度double。
第一趟合并（merge 1）調(diào)用了4次merge sorted array，得到了4個(gè)有序的數(shù)組："5, 8"，"3, 9"，"6, 4"，"1, 4"（每個(gè)合并后的序列長(zhǎng)度為2）
第二趟合并（merge 2）調(diào)用了2次merge sorted array，得到了2個(gè)有序的數(shù)組："3, 5, 8, 9"，"1, 4, 6, 11''（每個(gè)合并后的序列長(zhǎng)度為4）
3、按步驟1的思想以此類推，經(jīng)過多次合并最終得到有序的數(shù)組，也就是State3。
可以看出經(jīng)過一共3趟合并，最終得到有序的數(shù)組。
可以看出每趟要執(zhí)行的合并次數(shù)不同，第一趟合并執(zhí)行4次，第二趟合并執(zhí)行2次，第三趟合并行1次。
看了上述的算法思想，可以知道算法可以設(shè)計(jì)成兩層循環(huán)
- 外層循環(huán)遍歷趟數(shù)
- 內(nèi)層循環(huán)遍歷合并次數(shù)
但是我們會(huì)發(fā)現(xiàn)排序元素的個(gè)數(shù)不一定是2^i
如圖可知，一般數(shù)組元素的個(gè)數(shù)不一定是2i個(gè)。右邊多出的"10, 7, 2"子樹可以視作一般情況的情形。雖然元素個(gè)數(shù)不一定是2i個(gè)，但是任意元素個(gè)數(shù)的n，必然可以拆分成2j + m個(gè)元素的情形（數(shù)學(xué)條件不去深究）由圖可知，特殊情形思想中的兩兩合并的規(guī)則不能滿足一般情況的合并需求
- 圖中灰色的箭頭代表無需合并，因?yàn)檎也坏脚鋵?duì)的元素。
- 圖中墨藍(lán)色的箭頭代表兩個(gè)長(zhǎng)度不相等的元素也需要進(jìn)行合
將上述的合并需求稱為長(zhǎng)短合并，容易知道長(zhǎng)短合并僅存在1次或0次。
下面討論的合并前/后的序列長(zhǎng)度特指兩兩合并后得到的序列長(zhǎng)度。
合并循環(huán)設(shè)計(jì)：
雖然一般情形與特殊情形的合并規(guī)則有差別（一般情形復(fù)雜），但是可以設(shè)計(jì)一個(gè)通用的合 并趟數(shù)條件。
設(shè)置變量：記錄每趟合并后序列的長(zhǎng)度，其中k是趟次
- 通過觀察發(fā)現(xiàn)：每次合并后序列的大小有規(guī)律，第一趟后合并的序列大小都是2，第二趟合并后的序列大小都是4，以此類推..
- "10, 7, 2"這三個(gè)元素組合而成的序列長(zhǎng)度雖然不滿足上述的規(guī)律，但是并不影響趟數(shù)的計(jì)算。24 = 16 ≥ 11，4趟后循環(huán)結(jié)束。
- 可以設(shè)計(jì)成：if 最后合并后的序列長(zhǎng)度≥實(shí)際元素的個(gè)數(shù)n，這時(shí)可以說明循環(huán)結(jié)束
對(duì)應(yīng)代碼實(shí)現(xiàn)：
void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2) {
int i = begin1;
int index = begin1;
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 (; i <= end2; i++) {
a[i] = tmp[i];
}
}
void mergeSort(int* a, int n) {
int* tmp = new int[n];
int gap = 1;
while (gap < n) {
for (int i = 0; i < n; i+=2*gap) {
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (begin2 >= n) {//說明已經(jīng)排序完成
break;
}
if (end2 >= n) {//修正區(qū)間
end2 = n - 1;
}
_Merge(a, tmp, begin1, end1, begin2, end2);
}
gap *= 2;
}
delete[]tmp;
}
排序總結(jié)
如有錯(cuò)誤請(qǐng)指正?。。?！
到此這篇關(guān)于深入學(xué)習(xí)C語(yǔ)言中常見的八大排序 的文章就介紹到這了,更多相關(guān)C語(yǔ)言 八大排序 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++小知識(shí):C/C++中不要按值傳遞數(shù)組
今天小編就為大家分享一篇關(guān)于C++小知識(shí):C/C++中不要按值傳遞數(shù)組，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-01-01
2022最新使用VSCode編譯運(yùn)行C++的過程及會(huì)遇到的兩個(gè)問題
這篇文章主要介紹了2022最新使用VSCode編譯運(yùn)行C++的過程及會(huì)遇到的兩個(gè)問題,這里需要注意把剛才解壓的地址加上\bin添加進(jìn)去，比如我的：D:\aaakkk\cpp\mingw64\bin，然后點(diǎn)確定，注意一定要確保它被保存了，感興趣的朋友跟隨小編一起看看吧2022-09-09
QT獲取顯示當(dāng)前時(shí)間和日期的方法(用QTime,QDate和QDateTime)
獲取當(dāng)期日期時(shí)間在我們?nèi)粘ｉ_發(fā)中經(jīng)常會(huì)遇到,下面這篇文章主要給大家介紹了關(guān)于QT獲取顯示當(dāng)前時(shí)間和日期的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-08-08
寧可錯(cuò)殺一千,也不放過一個(gè),這是布隆過濾器的特點(diǎn),本文主要介紹了C++布隆過濾器的使用示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09
=error MSB3073是Visual Studio編譯器報(bào)出的錯(cuò)誤,本文主要介紹了VS編譯出現(xiàn)MSB3073命令的解決方案,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了VSCode插件開發(fā)全攻略之命令、菜單、快捷鍵,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05
C語(yǔ)言實(shí)現(xiàn)新生入學(xué)登記系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)新生入學(xué)登記系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要介紹了C語(yǔ)言規(guī)律循環(huán)累加求和案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
關(guān)于C++中構(gòu)造函數(shù)初始化成員列表的總結(jié)
下面小編就為大家?guī)硪黄P(guān)于C++中構(gòu)造函數(shù)初始化成員列表的總結(jié)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要為大家介紹了C++函數(shù)重載介紹與原理，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01