C語言實現快速排序的方法及優(yōu)化
更新時間：2023年07月11日 10:08:38 作者：碩碩C語言
這篇文章主要介紹了C語言實現快速排序的方法及優(yōu)化,快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法,下面我們來看一看傳說中的快速排序的特點與效率怎么樣,需要的朋友可以參考下
前言
在學數據結構的第一節(jié)課就知道了數據結構課程是要管理并且學會操作數據，當然操作數據首先想到的就是數據的排序，排過順序的數據的使用價值才夠大。前面我們學習了順序表也學習了鏈表等等，這些就是儲存數據的方法，下面我們來看一看傳說中的快速排序的特點與效率怎么樣
快速排序
快速排序，又稱劃分交換排序（partition-exchange sort）
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
實現邏輯
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
① 從數列中挑出一個元素，稱為 “基準”（pivot）
② 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數列的中間位置。這個稱為分區(qū)（partition）操作。
③ 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
// 假設按照升序對array數組中[left, right)區(qū)間中的元素進行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基準值對array數組的 [left, right)區(qū)間中的元素進行劃分
int div = partion(array, left, right);
// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)
// 遞歸排[left, div)
QuickSort(array, left, div);
// 遞歸排[div+1, right)
QuickSort(array, div+1, right);
}上述為快速排序遞歸實現的主框架，發(fā)現與二叉樹前序遍歷規(guī)則非常像，同學們在寫遞歸框架時可想想二叉樹前序遍歷規(guī)則即可快速寫出來，后序只需分析如何按照基準值來對區(qū)間中數據進行劃分的方式即可。將區(qū)間按照基準值劃分為左右兩半部分的常見方式有：
1. hoare版本
代碼
int PartSort1(int* a, int begin, int end)
{
int left = begin, right = end;
int keyi = left;
while (left < right)
{
//右邊先走，找比a[keyi]小的
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊先走，找比a[keyi]大的
while (left < right && a[left] <= a[keyi])
{
left++;
}
//交換左右邊
Swap(&a[left], &a[right]);
}
//交換keyi與交點的值
Swap(&a[left], &a[keyi]);
keyi = left;
}2. 挖坑法
代碼
// 挖坑法
int PartSort2(int* a, int begin, int end)
{
int key = a[begin];
int piti = begin;
while (begin < end)
{
// 右邊找小，填到左邊的坑里面去。這個位置形成新的坑
while (begin < end && a[end] >= key)
{
--end;
}
a[piti] = a[end];
piti = end;
// 左邊找大，填到右邊的坑里面去。這個位置形成新的坑
while (begin < end && a[begin] <= key)
{
++begin;
}
a[piti] = a[begin];
piti = begin;
}
a[piti] = key;
return piti;
}3. 前后指針版本
代碼
int PartSort3(int* a, int begin, int end)
{
int keyi = begin;
int cur = begin + 1;
int prev = begin;
// 加入三數取中的優(yōu)化
int midi = GetMidIndex(a, begin, end);
Swap(&a[keyi], &a[midi]);
while (cur <= end)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[begin], &a[prev]);
keyi = prev;
return keyi;
}快速排序優(yōu)化
1. 三數取中法選key
當我們知道這組無序數列的首和尾后，我們便可以求出這個無需數列的中間位置的數，我們只需要在首，中，尾這三個數據中，選擇一個排在中間的數據作為基準值，進行快速排序，即可進一步提高快速排序的效率。那么為什么要取中間呢？我們可以假設待排序的數列是一組高度有序的數列，顯然首極大可能是最小值，尾極大可能是最大值，此時如果我們選取一個排在中間的值，哪怕是在最壞的情況下，begin和end只需要走到中間位置，那么這個中間值的位置也就確定下來，而不需要begin或end指針要把整個數列遍歷一邊，從而大大提高快速排序的效率。即取數組最左端最右端以及數組中間三個數的中間數為分區(qū)點，減少采用左右端點碰到極端順序的出現的最壞情況（ 當選取左右端點，碰到數據有序，從大到小或是從小到大的情況 ，算法時間復雜度就會變成最壞時間復雜度）。
int GetMidIndex(int* a, int begin, int end) // 三數取中，優(yōu)化算法，避免發(fā)生最壞的情況
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return end;
}
else
{
return begin;
}
}
else // (a[begin] >= a[mid])
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}2. 遞歸到小的子區(qū)間時，可以考慮使用插入排序
序列長度達到一定大小時，使用插入排序當快排達到一定深度后，劃分的區(qū)間很小時，再使用快排的效率不高。當待排序列的長度達到一定數值后，可以使用插入排序。由《數據結構與算法分析》(Mark Allen Weiness所著)可知，當待排序列長度為5~20之間，此時使用插入排序能避免一些有害的退化情形。
void Qsort(int* a, int begin, int end)
{
if (begin >= end) return;
if (end - begin > 10)// 優(yōu)化二：在遞歸到剩余數據量小于一定值的時候跳出遞歸，進行小數據量的插入排序
{
int keyi = PartSort3(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
Qsort(a, begin, keyi - 1);
Qsort(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}
}快速排序非遞歸（用棧實現）
void QsortStack(int* a, int begin, int end){ST st;STInit(amp;st);STPush(amp;st, end);STPush(amp;st, begin);while (!STEmpty(amp;st)){int left #61; STTop(amp;st);STPop(amp;st);int right #61; STTop(amp;st);STPop(amp;st);int keyi #61; PartSort3(a, left, right);// [left, keyi-1] keyi[keyi#43;1, right]if (keyi #43; 1 lt; right){STPush(amp;st, right);STPush(amp;st, keyi #43; 1);}if (left lt; keyi - 1){STPush(amp;st, keyi - 1);STPush(amp;st, left);}}STDestroy(amp;st);}快速排序的特性總結
1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(logN)
4. 穩(wěn)定性：不穩(wěn)定
全部代碼
//快速排序
int PartSort1(int* a, int begin, int end)
{
int left = begin, right = end;
int keyi = left;
while (left < right)
{
//右邊先走，找比a[keyi]小的
while (left < right && a[right] >= a[keyi])
{
right--;
}
//左邊先走，找比a[keyi]大的
while (left < right && a[left] <= a[keyi])
{
left++;
}
//交換左右邊
Swap(&a[left], &a[right]);
}
//交換keyi與交點的值
Swap(&a[left], &a[keyi]);
keyi = left;
}
// 挖坑法
int PartSort2(int* a, int begin, int end)
{
int key = a[begin];
int piti = begin;
while (begin < end)
{
// 右邊找小，填到左邊的坑里面去。這個位置形成新的坑
while (begin < end && a[end] >= key)
{
--end;
}
a[piti] = a[end];
piti = end;
// 左邊找大，填到右邊的坑里面去。這個位置形成新的坑
while (begin < end && a[begin] <= key)
{
++begin;
}
a[piti] = a[begin];
piti = begin;
}
a[piti] = key;
return piti;
}
int GetMidIndex(int* a, int begin, int end) // 三數取中，優(yōu)化算法，避免發(fā)生最壞的情況
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return end;
}
else
{
return begin;
}
}
else // (a[begin] >= a[mid])
{
if (a[mid] > a[end])
{
return mid;
}
else if (a[begin] < a[end])
{
return begin;
}
else
{
return end;
}
}
}
int PartSort3(int* a, int begin, int end)
{
int keyi = begin;
int cur = begin + 1;
int prev = begin;
// 加入三數取中的優(yōu)化
int midi = GetMidIndex(a, begin, end);
Swap(&a[keyi], &a[midi]);
while (cur <= end)
{
if (a[cur] < a[keyi])
{
prev++;
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[begin], &a[prev]);
keyi = prev;
return keyi;
}
void Qsort(int* a, int begin, int end)
{
if (begin >= end) return;
if (end - begin > 10)// 優(yōu)化二：在遞歸到剩余數據量小于一定值的時候跳出遞歸，進行小數據量的插入排序
{
int keyi = PartSort3(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
Qsort(a, begin, keyi - 1);
Qsort(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}
}
void QsortStack(int* a, int begin, int end)
{
ST st;
STInit(&st);
STPush(&st, end);
STPush(&st, begin);
while (!STEmpty(&st))
{
int left = STTop(&st);
STPop(&st);
int right = STTop(&st);
STPop(&st);
int keyi = PartSort3(a, left, right);
// [left, keyi-1] keyi[keyi+1, right]
if (keyi + 1 < right)
{
STPush(&st, right);
STPush(&st, keyi + 1);
}
if (left < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, left);
}
}
STDestroy(&st);
}到此這篇關于C語言實現快速排序的方法及優(yōu)化的文章就介紹到這了,更多相關C語言快速排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現密碼本，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
c語言中malloc、realloc與calloc 的區(qū)別以及聯系
以下是對c語言中的malloc函數，realloc函數與calloc函數的區(qū)別以及它們之間的聯系進行了介紹，需要的朋友可以過來參考下2013-08-08
今天小編就為大家分享一篇關于數據結構與算法:單向鏈表實現與封裝，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要為大家詳細介紹了C語言如何利用鏈表實現學生成績管理系統，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-11-11
這篇文章主要為大家詳細介紹了C++中的運算符重載的相關資料，文中的示例代碼講解詳細，對我們學習C++有一定幫助，需要的可以參考一下2022-09-09
這篇文章主要為大家介紹了C++中的const和constexpr ，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
這篇文章主要為大家詳細介紹了C++基于easyx實現迷宮游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了C++ 動態(tài)庫導出函數名亂碼及解決，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
這篇文章主要為大家詳細介紹了Qt實現部件透明陰影效果與不規(guī)則窗體的相關方法，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2023-01-01
C++11這次的更新帶來了令很多C++程序員期待已久的for?range循環(huán)，每次看到javascript，?lua里的for?range，心想要是C++能有多好，心里別提多酸了。這次C++11不負眾望，再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法2022-04-04