目錄
算法概述
圖示
偽代碼
選主元
子集劃分
小規(guī)模數(shù)據(jù)的處理
算法實(shí)現(xiàn)
算法概述
圖示
快速排序和歸并排序有一些相似，都是用到了分而治之的思想：
偽代碼
?
通過(guò)初步的認(rèn)識(shí)，我們能夠知道快速排序算法最好的情況應(yīng)該是：
每次都正好中分，即每次選主元都為元素的中位數(shù)的位置。
最好情況的時(shí)間復(fù)雜度為
選主元
假設(shè)我們把第一個(gè)元素設(shè)為主元，看以下的一種特殊情況：
?選了第一個(gè)元素為主元之后，掃描所有元素所用時(shí)間復(fù)雜度為O(N),然后還有N-1個(gè)元素要進(jìn)行遞歸，時(shí)間復(fù)雜度記為T(mén)(N-1)，所以最終它的時(shí)間復(fù)雜度為：
既然這種方法不行，那如果我們隨機(jī)取pivot呢？
很顯然，rand（）函數(shù)的時(shí)間效率是很低的，當(dāng)然也不考慮。
所以我們就想，
取頭、中、尾的中位數(shù)，例如取三個(gè)數(shù)的中位數(shù)：8、12、3的中位數(shù)就是8；或者五個(gè)數(shù)選取中位數(shù)等等。
下面就是三個(gè)數(shù)中選取中位數(shù)的算法：
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此時(shí)A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 將基準(zhǔn)Pivot藏到右邊*/
/* 只需要考慮A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基準(zhǔn)Pivot */
}
?選好基準(zhǔn)之后，我們就進(jìn)入子集的劃分。
子集劃分
注意：如果有元素正好等于pivot時(shí)，則停下來(lái)進(jìn)行交換。
小規(guī)模數(shù)據(jù)的處理
快速排序有一個(gè)比較明顯的問(wèn)題，那就是用遞歸，而遞歸需要頻繁地調(diào)用棧；在小規(guī)模數(shù)據(jù)的處理上不占優(yōu)勢(shì)。
也就是說(shuō)，對(duì)小規(guī)模的數(shù)據(jù)（例如N不到100）可能還不如插入排序快。
解決方案
- 當(dāng)遞歸的數(shù)據(jù)規(guī)模充分小時(shí)，則停止遞歸，直接調(diào)用簡(jiǎn)單排序（例如插入排序）
- 在程序中定義一個(gè)Cutoff的閾值
算法實(shí)現(xiàn)
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此時(shí)A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 將基準(zhǔn)Pivot藏到右邊*/
/* 只需要考慮A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基準(zhǔn)Pivot */
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心遞歸函數(shù) */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，進(jìn)入快排 */
Pivot = Median3( A, Left, Right ); /* 選基準(zhǔn) */
Low = Left; High = Right-1;
while (1) { /*將序列中比基準(zhǔn)小的移到基準(zhǔn)左邊，大的移到右邊*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 將基準(zhǔn)換到正確的位置 */
Qsort( A, Left, Low-1 ); /* 遞歸解決左邊 */
Qsort( A, Low+1, Right ); /* 遞歸解決右邊 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用簡(jiǎn)單排序 */
}
void QuickSort( ElementType A[], int N )
{ /* 統(tǒng)一接口 */
Qsort( A, 0, N-1 );
}end文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-609483.html
學(xué)習(xí)自：MOOC數(shù)據(jù)結(jié)構(gòu)——陳越、何欽銘文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-609483.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法——快速排序（算法概述、選主元、子集劃分、小規(guī)模數(shù)據(jù)的處理、算法實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
