- 快速排序
int Partion(vector<int> &vec, int lo, int hi)
{
int i = lo;
int j = hi;
int targetNum = vec[lo];
while(true)
{
while(vec[i] <= targetNum && i < hi) // 找到大于 targetNum
i++;
while(vec[j] >= targetNum && j > lo) // 找到小于 targetNum
j--;
if (i < j)
swap(vec[i], vec[j]);
else
break;
}
swap(vec[j], vec[lo]);
return j;
}
void QuickSort(vector<int> &vec, int lo, int hi)
{
if (lo < hi)
{
int j = Partion(vec, lo, hi);
QuickSort(vec, lo, j-1);
QuickSort(vec, j+1, hi);
}
}
-
優(yōu)化
三點(diǎn)中值
快速排序的效率與切分有很大關(guān)系诸迟，在選擇樞軸時(shí)塔鳍，我們可以采用取整 個(gè)序列的頭壹粟，尾拜隧，中央3個(gè)位置的元素，再以其中值最為樞軸趁仙，這種做法被稱為median-of-three partitioning洪添。加入插入排序
在快速排序塊要完成的時(shí)候，這時(shí)候序列已經(jīng)大部分已經(jīng)處于有序的狀態(tài)雀费，這時(shí)候我們再采用插入排序是會有更高的效率干奢。STL中的sort即是采用此方法。
應(yīng)用1：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
數(shù)組中有1個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半盏袄，那么假設(shè)把這個(gè)數(shù)組排序忿峻，那么排序之后的位于數(shù)組中間的數(shù)字一定就是那個(gè)出現(xiàn)次數(shù)超過數(shù)組長度一半的數(shù)字。（中位數(shù)）
受快速排序partion的啟發(fā)辕羽，我們先選隨機(jī)選擇一個(gè)數(shù)執(zhí)行一次partion逛尚。
如果它的下標(biāo)等于n/2，那么它就是中位數(shù)逛漫。
如果它的下標(biāo)小于n/2黑低，那么中位數(shù)一定在右半邊，繼續(xù)在它的右半邊查找。
如果它的下標(biāo)大于n/2克握，那么中位數(shù)一定在左半邊蕾管，繼續(xù)在它的左半邊查找。
/* 以下假定存在出現(xiàn)次數(shù)超過一半的數(shù)字 */
int MoreThanHalfNum(vector<int> vec, int middle)
{
int j = Partion(vec, 0, vec.size()-1);
while(j != middle)
{
if (j > middle)
j = partion(vec, 0, j-1);
else
j = partion(vec, j+1, vec.size()-1);
}
return vec[j];
}
應(yīng)用2：第k大的數(shù)
受上題的啟發(fā)菩暗，我們發(fā)現(xiàn)Partion之后掰曾，就可以確定第k大的數(shù)（j）。
/* 從0開始排名 */
int Knums(vector<int> vec, int k)
{
if (k < 0 || k >= vec.size())
throw ("參數(shù)超出范圍");
int j = partion(vec, 0, vec.size()-1);
if (k == j)
return vec[j];
while(j != k)
{
if (j > k)
j = partion(vec, 0, j-1);
else
j = partion(vec, j+1, vec.size()-1);
}
return vec[j];
}
應(yīng)用3：最小的k個(gè)數(shù)
同樣受上題的啟發(fā)停团，經(jīng)過一次Partion之后旷坦，樞軸前面的數(shù)比它小，樞軸后面的數(shù)比它大佑稠。
