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ù)的使用價值才夠大。前面我們學(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）策略來把一個序列（list）分為兩個子序列（sub-lists）。
① 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）
② 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
③ 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
// 假設(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é)們在寫遞歸框架時可想想二叉樹前序遍歷規(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)
{
// 右邊找小，填到左邊的坑里面去。這個位置形成新的坑
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;
// 加入三數(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ù)列的首和尾后，我們便可以求出這個無需數(shù)列的中間位置的數(shù)，我們只需要在首，中，尾這三個數(shù)據(jù)中，選擇一個排在中間的數(shù)據(jù)作為基準(zhǔn)值，進(jìn)行快速排序，即可進(jìn)一步提高快速排序的效率。那么為什么要取中間呢？我們可以假設(shè)待排序的數(shù)列是一組高度有序的數(shù)列，顯然首極大可能是最小值，尾極大可能是最大值，此時如果我們選取一個排在中間的值，哪怕是在最壞的情況下，begin和end只需要走到中間位置，那么這個中間值的位置也就確定下來，而不需要begin或end指針要把整個數(shù)列遍歷一邊，從而大大提高快速排序的效率。即取數(shù)組最左端最右端以及數(shù)組中間三個數(shù)的中間數(shù)為分區(qū)點(diǎn)，減少采用左右端點(diǎn)碰到極端順序的出現(xiàn)的最壞情況（ 當(dāng)選取左右端點(diǎn)，碰到數(shù)據(jù)有序，從大到小或是從小到大的情況 ，算法時間復(fù)雜度就會變成最壞時間復(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ū)間時，可以考慮使用插入排序
序列長度達(dá)到一定大小時，使用插入排序當(dāng)快排達(dá)到一定深度后，劃分的區(qū)間很小時，再使用快排的效率不高。當(dāng)待排序列的長度達(dá)到一定數(shù)值后，可以使用插入排序。由《數(shù)據(jù)結(jié)構(gòu)與算法分析》(Mark Allen Weiness所著)可知，當(dāng)待排序列長度為5~20之間，此時使用插入排序能避免一些有害的退化情形。
void Qsort(int* a, int begin, int end)
{
if (begin >= end) return;
if (end - begin > 10)// 優(yōu)化二：在遞歸到剩余數(shù)據(jù)量小于一定值的時候跳出遞歸，進(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. 時間復(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)
{
// 右邊找小，填到左邊的坑里面去。這個位置形成新的坑
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) // 三數(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ù)量小于一定值的時候跳出遞歸，進(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)文章
指向類成員的指針總的來講可以分為兩大類四小類（指向數(shù)據(jù)成員還是成員函數(shù)，指向普通成員還是靜態(tài)成員）2020-03-03
Visual Studio Code上添加小程序自動補(bǔ)全插件的操作方法
這篇文章主要介紹了Visual Studio Code上添加小程序自動補(bǔ)全插件的操作方法,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
C++統(tǒng)計中英文大小寫字母、數(shù)字、空格及其他字符個數(shù)的方法
這篇文章主要介紹了C++統(tǒng)計中英文大小寫字母、數(shù)字、空格及其他字符個數(shù)的方法,涉及C++字符串的遍歷與簡單判定技巧,具有一定參考借鑒價值,需要的朋友可以參考下2016-05-05
折半查找法也叫做二分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪一半中,再重復(fù)上述步驟知道找到目標(biāo)key,這篇文章主要給大家介紹了關(guān)于C語言二分查找的相關(guān)資料,需要的朋友可以參考下2023-04-04
C++中處理異常的過程是這樣的：在執(zhí)行程序發(fā)生異常，可以不在本函數(shù)中處理，而是拋出一個錯誤信息，把它傳遞給上一級的函數(shù)來解決，上一級解決不了，再傳給其上一級，由其上一級處理2013-08-08
這篇文章主要為大家詳細(xì)介紹了基于樹莓派實(shí)現(xiàn)播放MP3音樂，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
C/C++?Qt?Dialog?對話框組件應(yīng)用技巧
這篇文章主要介紹了C/C++?Qt?Dialog?對話框組件應(yīng)用,這里我將總結(jié)本人在開發(fā)過程中常用到的標(biāo)準(zhǔn)對話框的使用技巧，對C++?對話框組件相關(guān)知識感興趣的朋友一起看看吧2021-11-11
浮點(diǎn)數(shù)在計算機(jī)中存儲方式是怎樣的
這篇文章介紹了浮點(diǎn)數(shù)在計算機(jī)中是如何存儲的，講解的比較詳細(xì)，有需要的朋友可以參考一下。2016-06-06
本文主要介紹了C++友元函數(shù)和友元類的使用與區(qū)別，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
這篇文章主要介紹了C語言如何在字符數(shù)組中插入一個字符，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06