數據結構之經典八大排序的實現(萬字詳談）-創新互聯
- 前言
- 1.插入排序
- 2.希爾排序
- 3.選擇排序
- 4.堆排序
- 5.冒泡排序
- 6.快速排序
- hoare方式版本快排實現
- 非遞歸方式實現快排
- 挖坑法實現快排
- 前后指針法(雙指針法）
- 快排的各種優化
- 1.減少后幾層的遞歸調用(小區間優化）
- 2.三數取中優化
- 3.三路劃分(處理大量重復數據）
- 7.歸并排序
- 1.遞歸實現歸并排序
- 2.歸并排序的非遞歸實現
- 8.計數排序
- 9.額外知識關于各類排序算法的穩定性
- 10.總結
排序是對一種比較常見的對數據處理方式。排序算法在計算機領域中應用廣泛且重要。本文主要對幾種比較經典的排序算法進行講解，之前對冒泡排序和堆排序有過講解，本文也會回顧一下這兩種排序算法。(本文動圖均來自菜鳥教程，如有侵權聯系可刪）
1.插入排序
基本思想：直接插入排序是一種簡單的插入排序法，把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
其實我們玩撲克牌的時候就用了插入排序的思想，在起牌時數值較大的排往后放，數值較小的牌往前放。起排結束后手里的牌就按一定的順序排列了。
聯想玩牌時插入，6暫時放在13的后面，從尾到頭進行比較。6比13大，13到6的位置上，6往前走到13原來的位置接著比較；6比10大，6往前走，10往后走，接著比較；6比9小，6往前走，9往后走，接著比較。6比7小，7往后走，6往前走，接著比較；6比4大，6走到了合適的位置，插入過程結束。
這是模擬一次插入過程，當然我知道數組中數據不一定是有序的，所以我們假設第一個元素就是有序的，依次對往后的數據進行插入排序，整個插入插入過程就是有序的了。這就相當于假設起牌時第一張就是有序的，后序起到的牌依次進行調整。
我們先將的一趟的插入寫出來
對比著上面圖中的插入流程，一躺插入就可以確定了。完整的插入流程是從第一個元素開始重復上述插入比較流程，所以外層套個循環整個插入排序就寫出來了。
完整代碼示例
void InsertSort(int* a, int n)
{for (int i = 0;iint end = i;
//防止越界i= 0)
{ if (a[end] >tem)
{ a[end + 1] = a[end];
end--;
}
else
{ break;
}
}
a[end+1] = tem;
}
} 插入排序的時間復雜度我們分析一下
總的來說插入排序的時間復雜度是O(n^2),空間復雜度是O(1)
2.希爾排序
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數作為間距，把待排序數據按間距分成個組，并對每一組內的記錄進行插入排序。然后不斷縮小間距重復上述分組和排序的工作。當到間距==1時，進行最后一次排序。
上述的操作基本可以分為兩步：1.預排序（不斷縮小間距分組進行插入排序）;2.間距為1時最后一次排序（也就是直接進行插入排序）
我們畫圖分析一下：
這個間距劃分只要數組中元素位置滿足條件就可以歸為同一組。圖中第一組從2位置劃到3位置時，3往后的間距不夠5了所以就沒有接著劃分了。第二組劃分從2開始接著是7，最后到10，10后面只有一個位置，不滿足間距劃分條件。
那么代碼怎么寫呢？希爾排序本質還是采用插入排序，唯一的區別就是插入排序的區間被劃分了出來。確定了排序區間希爾排序就寫出來了。我們從圖可以看出其實起始還是從第一個元素開始，分組時第一個元素后面的第二個元素就是要插入的元素，第一次區間劃分時，2后面要插入的是3；第二次區間劃分時，分組中2后面是7。通過觀察發現插入的元素和第一個元素相差了一個間距的距離。這就確定了end后面不再是加1，而是在end基礎上加上間距。
代碼示例
void ShellSort(int* arr, int n)
{int gap = n;
while (gap >1)
{//這個間距+1確保最后一次gap為1
gap = gap / 3 + 1;
for (int i = 0; i< n - gap; i++)
{ int end = i;
int tem = arr[end + gap];
while (end >= 0)
{ if (tem< arr[end])
{arr[end + gap] = arr[end];
end-=gap;
}
else
{break;
}
}
arr[end + gap] = tem;
}
}
}我們發現如果gap==1，上述代碼就是插入排序。通過gap分組預排序會使數據越來越趨近于有序。當間距gap越來越小時，數據也會越來越有序。數據越有序，插入排序的性能越好。希爾排序就是根據這一特點在插入排序的基礎上延申出了預排序。因為每次gap先進行更新再執行排序邏輯，循環條件也應該是gap>1,不用取等。當然gap每次縮小3倍所以為了保證最后的結果為1，需要加1。如果gap=gap/2就不用加1，這樣除2，無論gap為何值最后的結果一定是1.
希爾排序的時間復雜度很不算，需要用到高等數學進行推導。所以只用記住希爾排序的時間復雜度為O(n^1.3),空間復雜度為O(1)
3.選擇排序
基本思想：每一次從待排序的數據元素中選出最小（或大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完 。
選擇排序就是直接選出大或最小的元素放在合適的位置不過選擇排序選大元素和最小元素可以同時進行，畫圖詳解一下。
從圖中可以看出選擇排序就是每次選再一個區間范圍中選出大或者最小的元素移動到區間邊界的位置上去。每次處理一趟過后，區間就會相應的縮小。直到區間范圍重合時，這個排序過程就結束了。
代碼示例
//交換函數
void swap(int* a, int* b)
{int tem = *a;
*a = *b;
*b = tem;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;
while (begin< end)
{int max = begin, min = begin;
//找最小元素和大元素的位置
for (int i = begin + 1; i<= end; i++)
{ if (a[max]< a[i])
{ max = i;
}
if (a[min] >a[i])
{ min = i;
}
}
swap(&a[begin], &a[min]);
//防止begin和max重合
if (begin == max)
{ max = min;
}
swap(&a[end], &a[max]);
end--;
begin++;
}
}這個交換函數需要自己寫。同時如果begin剛好和max重合或者end和min重合，因為交換順序的問題可能會造成bug，所以重要單獨處理，只針對一種情況判斷處理即可。根據代碼中的交換順序設置不同的判斷，我這里是先交換的begin和min位置上的元素，所以判斷的是begin和max.
選擇排序的時間復雜度是O(n^2)，其實結合選擇排序思想來看，它的時間復雜度也就是等差數列求和，空間復雜度O(1).
4.堆排序
堆排序是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。
堆排序之前的博客有過介紹，這里就不畫圖分析了。它實現就是兩步，第一步對對數據建堆，第二步每次將堆頂數據換到末尾位置進行堆調整。
代碼示例
//向下調整
void AdjustDown(int* arr, int n,int parents)//向下調整
{//n的作用只是用來約束孩子和雙親防止越界
int child = parents * 2 + 1;
while (child< n)
{//保證child是指向大孩子的
if (child + 1< n && arr[child + 1] >arr[child])
{child++;
}
if (arr[parents]< arr[child])
{Swap(&arr[parents], &arr[child]);
parents = child;
child = parents * 2 + 1;
}
else
{break;
}
}
return;
}
//交換函數
void Swap(int* a, int* b)
{int tem = *a;
*a = *b;
*b = tem;
}
void HeapSort(int* a, int n)
{//建堆
for (int i = (n - 1 - 1) / 2; i>=0; i--)
{AdjustDown(a, n, i);
}
int end = n - 1;
while (end >0)
{Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
return;
}堆排序時間復雜度是O(N*logN),空間復雜度O(1).
堆排序具體介紹可以看之前寫的關于實現堆的博客
5.冒泡排序
基本思想：重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
每趟冒泡排序可以將搞定一個數，也就是讓較大的數依次到右端。這個冒泡排序排序我之前的博客也有介紹，這里就不畫圖分析了。
代碼示例
void BubbleSort(int* a, int n)
{for (int i = 0; i< n; i++)
{for (int j = 1; j< n - i; j++)
{ if ( a[j - 1]>a[j])
{ int tem = a[j - 1];
a[j - 1] = a[j];
a[j] = tem;
}
}
}
}冒泡排序算是一種比較簡單的排序算法，時間復雜度O(n^2),空間復雜度為O(1)。關于冒泡排序的具體介紹可以翻我之前的博客。
6.快速排序
hoare方式版本快排實現快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
快速排序是排序中的重點之一，同時排序有多個版本我們依次分析，首先來畫圖分析一下hoare版本的排序。
hoare版本的快排就是先選一個元素作為key值，然后用兩個變量left right分別指向數據的起始位置和末尾位置。該位置的數據元素分別和key值進行比較。left指向的值如果大于key就停下來，等right停下來的時候和right位置處的元素交換，否則就往下走。right指向的值如果小于key值就停下來，等left停下來來的時候和left位置處的元素交換，否則right就往下走。直到right和left相遇，相遇之后，如果最開始選的key是最左邊的元素，就把key位置和left位置上的元素進行交換，否則就是right位置。同時，注意如果選的是left做key，那么right先走比較，否則就是right后走。然后就是遞歸處理了。
但是要注意選誰做key，如果選最左邊的位置的元素做key，右邊一定先走。反之亦然。left和right并不是同時走的。如果左邊做key，right先走。遇到小于key的，right停住，left開始走，遇到大于key的值也停住，然后left和right位置上的元素進行交換。然后接著right先走，重復上述的過程。直到left和right相遇，key和left位置上的元素交換。
代碼示例
void swap(int* a, int* b)
{int tem = *a;
*a = *b;
*b = tem;
}
void QuickSort_1(int* a, int begin, int end)
{if (begin >end)
{return;
}
int left = begin;
int right = end;
int key = left;
while (left< right)
{//左邊作為key，右邊先走,反之亦然
while (left< right && a[right] >= a[key])
{ right--;
}
while (left< right && a[left]<= a[key])
{ left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
key = left;
QuickSort_1(a, begin, key - 1);
QuickSort_1(a, key + 1, end);
}這個遞歸條件就是begin>end，隨著區間不斷分隔，區間會范圍會越縮越小。當區間范圍不存在時就停止遞歸。誰做key，最后key就和誰交換。key就更新成誰，誰就后走。
快排很有優化方式，在介紹優化方式之前我們先介紹其他幾種快排的實現。 為了使代碼邏輯更加清晰，我們將排序處理邏輯封裝成一個函數。在快排內調用這個函數對區間進行處理即可。 代碼示例 c語言中沒有不提供數據結構的接口，所以需要直接實現棧的相關接口。我之前的博客有講棧的相關實現。 挖坑法比較容易理解，不滿足條件的就放入坑位，之后更新坑位。left和right相遇后，只用將key填入坑位，坑位是最后為key準備的。 雙指針實現快排就是用兩個變量，一前一后。如果走在前面的變量指向的元素小于key，后面的變量就向前一步走，再將這兩個變量指向的元素進行交換。之后前面的指針接著走，就是說無論何種情況前面的變量肯定會往前走。后面的變量只有在特定情況下才能走一步。前面的變量走完所有的位置后，key和后面變量指向的元素進行交換。 畫圖分析 代碼示例 遞歸調用可能有棧溢出的風險。我們可以在遞歸的最后幾層進行插入排序的處理。對分割出來的小區間進行優化。之前提到快排的遞歸調用類似于二叉樹的前序遍歷，每次遞歸調用都是以2的指數倍增長，所以最后幾層的調用占總調用的次數比例是很大的，最后3到5層的調用大概占總次數的80%，因此在最后幾層不用遞歸采用插入排序可以大大較少遞歸次數。 代碼示例 插入排序是需要自己去實現的，代碼中間區間范圍控制在15，也就是如果劃分的區間中有15個以內個數的數據就進行插入排序。 之前分析快排時間復雜度提到了如果每次選取的key都是較為中間的值，快排的效果非常好。所以我們將begin end和這個區間的中間位置的元素進行比較，選取中間的元素作為key。 代碼示例 這個3數取中就是在begin和end以及mid這3個位置選取中間大的元素作為key。但是實際上還是可以進行優化，這個mid是固定位置，mid位置應該更隨機一定比較好，這樣選到中間數作為key的概率就會大大增加。 可以做出如下改動： rand() % (b-a+1)+ a ，表示 a~b 之間的一個隨機整數。這樣產生的key就會較為隨機了。關于rand函數可以在官網文檔中進行查閱。 三路劃分大概的思想就是將劃分3個區間 [begin，key-1] [key] [key+1,end]。看似三個區間的劃分和之前沒區別，但是key這個區間中放入的都是和key相同的元素。這樣能夠處理有大量相同數據的情況，如果不將和key相同的元素劃分到同一區間中，一旦出現大量重復的元素，快排的效率其實是大幅度降低的。 代碼示例 代碼中通過引入一個變量cur實現區間的劃分，cur會將小于key的元素集中到左邊，大于key的元素集中到右邊，中間的位置留給等于key的元素。代碼中只是涉及left和right位置的元素移動，最后循環結束時并沒有將key交換移動。這里的循環條件是left<=right取等了，也就是說在循環中就已經處理了和key的交換。和cur交換時lcur要移動，開始時cur和left只差一個位置，cur不移動就可能在交換時造成元素覆蓋，影響結果。 綜上所述，快排的時間復雜度是N*logN到N^2之間，輔助空間是logN和N之間。這都取決于數據元素好壞的情況。 歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并. 歸并排序就是不斷拆分區間，當區間只有一個元素時就暫時認為它是有序的，再回頭對拆分出的區間排序合并。但是拆分出的區間數據需要用另一個臨時空間保存，這個臨時空間保存排序好了的元素數據。最后將臨時空間的數據在拷貝回原數組空間中即可。 這個不斷拆分區間的過程就需要用到遞歸。但是臨時空間的開辟只需要開一次即可，所以我們將排序邏輯拆開單獨寫成一個函數。在歸并排序的函數中調用這個排序邏輯即可。 歸并排序的遞歸是后序遍歷，所以不能像快排那樣很輕松借助額外的數據結構就能解決。這個時候我們直接用迭代的方式來解決。斐波那契數列相信很多人都寫過，斐波那契數列的非遞歸就是從頭開始算往前迭代。那我們也可以先從只有一個元素的的時候開始算，從也就當于區間分割到底了。定義一個變量用來控制區間范圍，從只有一個元素開始排序，區間范圍逐漸增大。這樣迭代著往前走。 代碼示例 上面的代碼有很多要注意的細節，我們來好好分析一下。 代碼大致思路： 細節注意(區間可能越界的處理） 像這種循環外的單次拷貝如果跳出循環可能會將一些隨機值拷貝到數組中或者造成將一些元素給覆蓋掉。這個時候只能修正區間了，需要后面的while(begin1 歸并排序的時間復雜度是N*logN，每次對區間進行二分可以劃分成logN次，同時每次對劃分出的小區間都會遍歷，相當于遍歷完了整個元素。空間復雜度需要臨時空間就是O(N). 計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。計算排序是將待排的數據映射到數組下標中，利用數組下標的順序性來達到排序的目的。之前講解力扣題時就用到了類似的做法，將數組元素轉成另一個數組的下標。計數排序也是類似的方法。 當然也可以不用calloc，直接寫成int count[max-min+1]={0};在賦值回去的時候需要將min加上。從代碼中可以看出復雜度：O(MAX(N,范圍))，空間復雜度：O(范圍)，這個范圍就是max-min+1 所謂穩定性就是，如果數組中有重復的元素，排序之后不影響相對位置就是穩定的排序。比如1 5 4 3 插入排序的穩定性 冒泡排序的穩定性 歸并排序 選擇排序的穩定性 希爾排序的穩定性 快排的穩定性 堆排序的穩定性 計數排序的穩定性 計數排序毫無疑問是沒有穩定性的，計數排序只關心元素出現的次數，無法控制相對順序。這點通過代碼或者它的排序思想就可以感受到。 你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
網頁名稱：數據結構之經典八大排序的實現(萬字詳談）-創新互聯
成都網站建設公司_創新互聯，為您提供虛擬主機、外貿網站建設、網站策劃、全網營銷推廣、電子商務、網站排名
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：
創新互聯
left快排的實現很像二叉樹的前序遍歷，先將要一趟排序處理的情況情況分析確定好，同時，確定遞歸邊界條件。剩下的就是對左半區間和對右半區間的遞歸處理。分析一下這個代碼時間復雜度。
非遞歸方式實現快排遞歸就是程序的重復調用，也就是說對每個問題的處理方式都是一樣的。對于快排的遞歸來說，每次排序的流程都是確定好的，遞歸主要是為了對分隔出的區間進行處理。我們只用借助別的數據結構將每次劃分的區間先存儲起來，在對每個區間進行同樣的排序處理即可。遞歸我們用的是函數棧幀，非遞歸實現我們就借助棧這種數據結構來實現。int QuickSort_2(int* a, int begin, int end)
{int left = begin;
int right = end;
int key = left;
while (left< right)
{while (left< right && a[right] >= a[key])
{ right--;
}
while (left< right && a[left]<= a[key])
{ left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
return left;
}
void QuickSortNonR(int* a, int begin, int end)
{//先建立棧
Stack st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{//先進去的是左區間后進的右區間，出來是先出右邊區間后出左區間
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int key = QuickSort_2(a, left, right);
//if判斷相當于之前的遞歸中止條件
//分割成只有一個數的區間事就不用繼續分隔割
if (left< key - 1)
{//前面已經確定先左后右，接著按這個順序
StackPush(&st, left);
StackPush(&st, key - 1);
}
if (key + 1< right)
{ StackPush(&st, key + 1);
StackPush(&st, right);
}
}
StackDestroy(&st);
}我們先將數組的整個的區間范圍入棧，在出棧區間調用函數排序處理。處理完了之后再進左右區間，直到棧中數據為空為止。注意入棧的順序。先入棧的后出棧。代碼中先入棧的是左邊界，后入棧的右邊界。所以先出棧的是右邊界，后出的左邊界。同時注意，每次數據出棧后都要Pop掉。之前遞歸的時候有遞歸邊界條件，現在是非遞歸所以要保證區間范圍的合法性，需要添加if判斷，合法的區間邊界才能入棧。
挖坑法實現快排挖坑法是在hoare版本的基礎進行的變形。其中元素比較的過程和left right移動過程差不多類似，但是它不涉及交換。它是用元素覆蓋也就是賦值的形式更新數據。挖洞法會先找一個位置為坑位，如果left和rigt指向的元素不滿足條件了就會將這個元素放入坑位。同時更新坑位，最后left和right相遇時，將key放入坑位。一般最開始選擇最左邊的位置作為坑位。/挖坑法寫快排 元素覆蓋挪動，不涉及位置上的元素交換
void QuickSort_2(int* a, int begin, int end)
{if (begin >end)
{return;
}
int left = begin;
int right = end;
int key = a[begin];
int hole = begin;
while (left< right)
{//左邊做key，右邊先走
while (left< right && a[right] >= key)
{ right--;
}
a[hole] = a[right];
hole = right;
while (left< right && a[left]<= key)
{ left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
int index = hole;
QuickSort_2(a, begin, index - 1);
QuickSort_2(a, index + 1, end);
}
前后指針法(雙指針法）
可以看出這樣的實現方法每次排序也可以分割區間和排定一個key。void swap(int* a, int* b)
{int tem = *a;
*a = *b;
*b = tem;
}
void QuickSort_3(int* a, int begin, int end)
{if (begin >end)
{return;
}
int cur = begin + 1;
int prev = begin;
int key = begin;
while (cur<= end)
{if (a[cur]< a[key] && ++prev != cur)
{ swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[prev], &a[key]);
QuickSort_3(a, begin, prev - 1);
QuickSort_3(a, prev + 1, end);
}
現在區間相當于分割成了[begin,prev-1] prev [prev+1,end]。代碼中可以看到加了++prev與cur判斷，這樣可以過濾無用的交換。
快排的各種優化
1.減少后幾層的遞歸調用(小區間優化）void swap(int* a, int* b)
{int tem = *a;
*a = *b;
*b = tem;
}
void QuickSort_1_2(int* a, int begin, int end)
{if (begin >end)
{return;
}
// 小區間用直接插入替代，減少遞歸調用次數
else if ((end - begin + 1)< 15)
{//插入排序的第二個參數是元素個數需要加1
//第二個參數的數組的起始空間地址，隨著區間的分割起始空間就是a+begin
InsertSort(a + begin, end - begin + 1);
}
int mid = GetMidIndex(a, begin, end);
swap(&a[begin], &a[mid]);
int left = begin;
int right = end;
int key = left;
while (left< right)
{while (left< right && a[right] >= a[key])
{ right--;
}
while (left< right && a[left]<= a[key])
{ left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
key = left;
QuickSort_1_2(a, begin, key - 1);
QuickSort_1_2(a, key + 1, end);
}
2.三數取中優化//得到較為中間的數
int GetMidIndex(int* a, int begin, int end)
{int mid = begin + (end - begin) / 2;
if (a[begin]< a[mid])
{if (a[mid]< a[end])
{ return mid;
}
else if (a[begin] >a[end])
{ return begin;
}
else
{ return end;
}
}
else
{if (a[begin]< a[end])
{ return begin;
}
else if (a[mid] >a[end])
{ return mid;
}
else
{ return end;
}
}
}
//三路取中優化快排
void QuickSort_1_1(int* a, int begin, int end)
{if (begin>end)
{return;
}
int mid = GetMidIndex(a, begin, end);
swap(&a[begin], &a[mid]);
int left = begin;
int right = end;
int key = left;
while (left< right)
{while (left< right && a[right] >= a[key])
{ right--;
}
while (left< right && a[left]<=a[key])
{ left++;
}
swap(&a[left], &a[right]);
}
swap(&a[left], &a[key]);
key = left;
QuickSort_1_1(a, begin, key - 1);
QuickSort_1_1(a, key + 1, end);
}
int mid = begin + rand()%(end-begin+1);
3.三路劃分(處理大量重復數據）
大致思路就是最開始cur指向left前一個位置，cur指向的元素大于key就和right交換，right退一步，cur不動。如果cur指向的元素小于key，cur和left交換，left和cur都向前一步。如果cur指向元素等于key,cur往前走就可以了。void QuickSort(int* a, int begin, int end)
{if (begin >end)
{return;
}
int left = begin;
int right = end;
int key = a[begin];
int cur = begin + 1;
while (cur<= right)
{if (a[cur]< key)
{ swap(&a[cur], &a[left]);
left++;
cur++;
}
else if (a[cur] >key)
{ swap(&a[cur], &a[right]);
right--;
}
else
{ cur++;
}
}
QuickSort(a, begin, left- 1);
QuickSort(a, right + 1, end);
}
對了，之前的幾種優化方法都可以寫在都一份快排代碼中，使得快排優化到最好成為名副其實的快排。
7.歸并排序
1.遞歸實現歸并排序
接著我們就思考排序邏輯怎么確定。區間每次都是在上一個區間基礎上二分出來的。假定有這么有個區間【begin，end】，二分之后就是【begin,mid】【mid+1,end】。這兩個區間就當于兩個數組，將兩個數組的元素進行排序合并到另一個數組中。之前的力扣習題有講解過類似的合并處理，我們用bgein1和begin2兩個變量開始指向區間元素的首部，然后依次比較。最后如果有一個區間的沒有比較完，直接將該區間的剩余元素接上直接放入臨時數組即可。
圖中的代碼邏輯就是排序的主要邏輯。因為歸并排序是先將數據分割成只有一個元素的區間，再排序合并。對于只有一個元素的區間來說，這個區間就是有序的。隨著不斷排序合并，臨時數組中的元素也會越來越有序。同時既然是遞歸那么遞歸邊界條件就是區間分隔成只有一個元素時停止，也就是begin==end.
那么代碼就很好寫了，代碼示例如下：void merge_sort_1(int* a, int* tem, int begin, int end)
{if (begin == end)
{return;
}
int mid = (begin + end) / 2;
merge_sort_1(a, tem, begin, mid);
merge_sort_1(a, tem, 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])
{ tem[i++] = a[begin1++];
}
else
{ tem[i++] = a[begin2++];
}
}
while (begin1<= end1)
{tem[i++] = a[begin1++];
}
while (begin2<= end2)
{tem[i++] = a[begin2++];
}
memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort_1(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);
if (tem == NULL)
{perror("malloc fail !");
return;
}
merge_sort_1(a, tem, 0, n - 1);
free(tem);
tem = NULL;
}
雖然快排和歸并排序都是分割區間遞歸。但是兩者還是有區別的，當數據是最開始的完整區間時，就可以進行排序處理。然后接著分割排序。但是歸并排序是將數據分隔成有一個元素的區間時，再回過頭來進行排序，也就是先分區間，再排序。快排是類似于先序遍歷，歸并相當于后序遍歷。
2.歸并排序的非遞歸實現void MergeSort_2(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);
if (tem == NULL)
{perror("malloc fail!");
return;
}
//歸并每組數據個數，從1開始，因為1個認為是有序的，可以直接歸并
int range = 1;
while (range< n)
{for (int i = 0; i< n; i += range * 2)
{ int begin1 = i, end1 = i + range - 1;
int begin2 = i + range, end2 = i + 2 * range - 1;
int j = i;
//對邊界條件處理防止越界
if (end1 >= n)
{ break;
}
else if (begin2 >= n)
{ break;
}
else if (end2 >= n)
{ end2 = n - 1;
}
while (begin1<= end1 && begin2<= end2)
{ if (a[begin1]<= a[begin2])
{tem[j++] = a[begin1++];
}
else
{tem[j++] = a[begin2++];
}
}
while (begin1<= end1)
{ tem[j++] = a[begin1++];
}
while (begin2<= end2)
{ tem[j++] = a[begin2++];
}
memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));
}
range *= 2;
}
free(tem);
tem = NULL;
}range控制區間范圍，之前是通過遞歸的方式來達到將區間分隔的目的。從區間只有一個元素開始逐漸擴大區間的范圍。排序邏輯和遞歸版的都是類似的，然后用拷貝函數將臨時數組拷貝到原數組中。拷貝可以放到除了放到循環里面每次拷貝外，還可以放到for循環外面整體拷貝，也就是將數據排序好了放入臨時數組中，再將臨時數組的拷貝到原數組。這里看到begin1=i,end1=i+range-1;begin2=i+range.end2=i+range*2-1;因為i始終是小于n的所以begin1沒有越界的風險。當數組的元素個數不是2的指數倍，就可能越界了。我們將每次劃分的區間打印出來，同時屏蔽掉防止區間越界的處理代碼
打印結果如下
我們看到打印如圖所示，沒啥問題。此時n的大小是8，如果我們將它換成10呢？
可以看到這里面有些區間已經越界了。對此，我們必須做出區間越界的處理。分析區間越界，無非就是以下幾種情況：首先bgein1不會越界，那么就是end1越界，如果end1越界后面的begin2和end2肯定必會越界。接著就是begin2越界，begin2越界后面的end2也肯定越界，最后一種情況就是只有end2越界了。所以分析下來只要處理3種情況即可，end1和begin2以及end2越界的處理。這里處理防止區間越界有兩種方式，一種是修正區間，還有一種是跳出循環。對于在循環里的每次拷貝來說，這兩種方法都可以，但是對于循環外的整體拷貝來說只能修正區間。
這個時候需要修正區間，將begin2和end2修正成一個不存在的區間。但是如果拷寫在for循環中就不用修正，直接跳出循環就可以。因為后續的拷貝還是這些元素，不影響后續的排序拷貝。接著處理begin2越界的情況,begin2的越界的話，begin2和end2都是錯誤區間，對于在for循環中的分組多次拷貝來說直接break即可。如果對于在循環外整體拷貝來說就需要修正區間將begin2和end2改成不存在的區間即可。因為后續的begin1和end1區間內的元素是需要放進臨時空間的。最后就是end2越界了，end2越界，劃分的區間中肯定有一部分是屬于正常的范圍內，對于end2來說只能采用修正區間的方法，不能跳過，否則最后一段區間就不會排序進入臨時空間，造成排序的不完整。不管memcpy拷貝寫在何處，end需要修正成n-1。這樣才能正確排好序。
8.計數排序計數排序通過將數組元素轉成另一個數組的下標來排序，這里就需要臨時空間了，為了節省空間。我們直接將空間范圍確定為0到待排數組元素中大值max與最小值min差值加1，也就是max-min+1.
代碼示例void CountSort(int* a, int n)
{int max = a[0];
int min = a[0];
int i = 0;
for (i=1; i< n; i++)
{if (a[i] >max)
{ max = a[i];
}
if (a[i]< min)
{ min = a[i];
}
}
int* count=(int*)calloc(max-min+1,sizeof(int));
if (count == NULL)
{perror(" calloc fail!");
return;
}
for (i=0; i< n; i++)
{count[a[i] - min]++;
}
int k = 0;
for (i = 0; i< max-min+1; i++)
{while (count[i]--)
{ a[k++] = min+i;
}
}
free(count);
count = NULL;
}計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限。只是適用于對整型(負整型也可以)排序。
9.額外知識關于各類排序算法的穩定性46排序之后應該是1 3 445 6，紅色的4在后面要保持相對位置不變。接著我們來討論討論上述8種算法的穩定性。插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。剛開始這個有序的小序列只有1個元素，就是第一個元素，插入的元素從end后開始比較往前移動。如果end位置的元素和要插入的元素相等，可以將相等或者大于a[end]放入end的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定排序算法。冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，沒有動作；兩個相同元素就算有間隔也不影響，隨著不斷挪動相相同的元素會相鄰，又回到了相鄰元素相等沒有交換。冒泡也是穩定的。歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素或者2個序列，然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發現，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩定性。那么，在短的有序序列合并的過程中，穩定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結果序列的前面，這樣就保證了穩定性。所以，歸并排序也是穩定的排序算法。選擇排序是一種不穩定的排序方式，當數組中出現重復元素了，在找max和min的位置后會和begin end位置元素進行交換，當交換的位置是某個重復元素的為止時，原有順序就會被破壞，從而影響相對順序.
希爾排序也是不穩定的，希爾排序的先進行預分組的方式排序，在進行預分組的時候隨著區間的跳動是沒法控制相同元素的相對位置的。相同的元素可能會因為預處理的時候被從前面移動到后面將原有的順序打亂快排也是不穩定的，我們知道快排每次都選key，如果有相同的元素且它們大于key話,它們會集中到key的右側，中間會涉及到交換，先出現的元素會被放到后面，后出現的元素會被放到前面，這樣相對位置就會被影響。同時，如果相同的元素做key，因為最后要交換key，前面做key的元素也會被移動到后面。堆排序也是不穩定的，以建大堆為例，假如建堆的時候就保證了順序的穩定性，但是堆頂的數據會被移動到數組后面的位置，等到另一個相同的元素作為堆頂的時候就會被放入靠前面的位置，這樣穩定性就被破壞了。
10.總結
標題鏈接：http://vcdvsql.cn/article14/ccsige.html
- 教你認識什么是符合Google規則的網站？ 2016-09-26
- 21種技術和技巧Google Ads投放谷歌規劃師運用 2023-05-05
- 江蘇網站建設谷歌代理商告訴你通過 Google AdMob 展示相關廣告，從數以百萬計的廣告主那里獲 2016-03-24
- Google優化推廣的重要性，品牌大于品質！ 2016-03-08
- 在線翻譯服務：百度研發2年，功能仍不及google 2016-07-01
- 百度已經正式支持 Google AMP 頁面數據提交 2020-09-06
- 講述一下google和百度優化之間的差異化 2016-01-23
- Google成功之謎 2016-05-18
- 任何產品都適合google推廣嗎？ 2016-04-18
- Google最新收錄規則，怎樣才能讓網站快速被Google收錄 2015-02-07
- Google優化還是谷歌推廣最好的選擇嗎？ 2016-04-17
- SEO與廣告結合可以得到更好的google推廣效果 2016-03-18