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