一宴胧、partition quicksort 分治+遞歸
快速排序一次劃分算法偽代碼:
將i和j分別指向待排序列最左記錄與最右側(cè)記錄;
重復(fù)下述過程,直到i = j;
右側(cè)掃描,j--,直到a[j] ? ? ? ? ? ? ? ? ? 表示前面已經(jīng)排行
左側(cè)掃描,直到a[i]>a[j],交換,j--; ? 表示前面已經(jīng)排好
循環(huán)結(jié)束,i = j,返回i的位置.
二猛蔽、快速排序可用于求第k個(gè)最大值
用O(n)的平均時(shí)間復(fù)雜度從無序數(shù)組中尋找第k大的值.和快排一樣,這里也用到了分而治之的思想.思路是,首先對(duì)數(shù)組進(jìn)行一次Partition,得到坐標(biāo)nPos:
如果nPos+1 == k,返回array[nPos];
如果nPos+1 > k,對(duì)數(shù)組左半部分繼續(xù)進(jìn)行Partition;
如果nPos+1 < k, 對(duì)數(shù)組右半部分繼續(xù)進(jìn)行Partition.
// 利用Partition實(shí)現(xiàn)復(fù)雜度為O(n)的尋找數(shù)組中第K大的數(shù)
int GetArrayMaxK(int array[], int nStart, int nEnd, int k)
{
if (k <= 0)
{
throw;
}
int nPos = -1;
while (true)
{
nPos = Partition(array, nStart, nEnd);
if ((nPos+1) == k)
{
return array[nPos];
}else if ((nPos+1) > k)
{
nEnd = nPos - 1;
}else
{
nStart = nPos + 1;
}
}
}
三初斑、partition進(jìn)階
荷蘭國旗問題
（可以以紅白藍(lán)為數(shù)字代替，統(tǒng)計(jì)數(shù)字，重新分配）
一種思路
我們可以把數(shù)組分成三部分，前部（全部是0）冕屯，中部（全部是1）和后部（全部是2）三個(gè)部分，每一個(gè)元素（紅白藍(lán)分別對(duì)應(yīng)0拂苹、1安聘、2）必屬于其中之一。
將前部和后部各排在數(shù)組的前邊和后邊，中部自然就排好了浴韭。
設(shè)置兩個(gè)指針begin指向前部（不是按0丘喻，1，2的個(gè)數(shù)區(qū)分的前后部）的末尾的下一個(gè)元素（相當(dāng)于）（剛開始默認(rèn)前部無0念颈，所以指向第一個(gè)位置）泉粉，end指向后部開頭的前一個(gè)位置（剛開始默認(rèn)后部無2，所以指向最后一個(gè)位置）舍肠，然后設(shè)置一個(gè)遍歷指針current搀继，從頭開始進(jìn)行遍歷窘面。
（1）若遍歷到的位置為1翠语，則說明它一定屬于中部，根據(jù)總思路财边，中部的我們都不動(dòng)肌括，然后current向前移動(dòng)一個(gè)位置。
（2）若遍歷到的位置為0酣难，則說明它一定屬于前部谍夭，于是就和begin位置進(jìn)行交換，然后current向前移動(dòng)一個(gè)位置憨募，begin也向前移動(dòng)一個(gè)位置（表示前邊的已經(jīng)都排好了）紧索。
（3）若遍歷到的位置為2，則說明它一定屬于后部菜谣，于是就和end位置進(jìn)行交換珠漂，由于交換完畢后current指向的可能是屬于前部的，若此時(shí)current前進(jìn)則會(huì)導(dǎo)致該位置不能被交換到前部尾膊，所以此時(shí)current不前進(jìn)媳危。而同1），end向前移動(dòng)一個(gè)位置冈敛。
void quick(int a[], int first, int end)
{
int current=first;
int temp;
while (current <= end)
{
if (a[current] == 1)
{
current++;
}
else if (a[current] == 0)
{
temp = a[first];
a[first] = a[current];
a[current] = temp;
first++;
current++;
}
else if (a[current] == 2)
{
temp = a[end];
a[end] = a[current];
a[current] = temp;
end--;
}
}
}
三路快速排序
算法原理：使用三路劃分策略對(duì)數(shù)組進(jìn)行劃分（也就是荷蘭國旗問題待笑，dutch national flag problem）。這個(gè)實(shí)現(xiàn)是對(duì)實(shí)現(xiàn)二的改進(jìn)抓谴，它添加處理等于劃分元素的值的邏輯峦耘，將所有等于劃分元素的值集中在一起，并且以后都不會(huì)再對(duì)他們進(jìn)行劃分所刀。本算法中使用四個(gè)標(biāo)示值進(jìn)行操作憔四。使用left和right同時(shí)向中間遍歷時(shí)，當(dāng)left遇見等于劃分元素時(shí)措拇，就與iflag指向的值進(jìn)行交換（iflag指向的當(dāng)前值到最左端表示left在過程中遇見的等于劃分元素的值部分）我纪，同理，右邊也使用同樣的邏輯完成對(duì)等于劃分元素的處理。最后分別交換左右部分的相等值（left和iflag對(duì)應(yīng)交換浅悉，right和rflag對(duì)應(yīng)交換）趟据，由于需要返回兩個(gè)標(biāo)記值，所以將partition和quicksort合并成一個(gè)方法术健。
? 算法代碼：
void quickSort_3(int *array, int l, int r) {
/**
* 由于三路劃分中有可能有兩個(gè)不同的劃分點(diǎn)汹碱，所以不能
* 使用函數(shù)直接返回，這里將partition和quickSort驅(qū)動(dòng)
* 程序結(jié)合成一個(gè)方法荞估；
* */
if(l>=r) return;
/**
* 選擇pivot劃分元素咳促，并將其與array[r]交換
* */
int pivot, temp;
pivot=l+rand()%(r-l+1);
temp=array[pivot];
array[pivot]=array[r];
array[r]=temp;
/**
* 雙向掃描：
* left和right都為主動(dòng)移動(dòng)
* lflag和rflag為被動(dòng)移動(dòng)
* */
int left=l, lflag=l;
int right=r-1, rflag=r-1;
while(true) {
while(array[left]<=array[r] && left
/**
* 如果array[left]與pivot相等，則將其交換到
* lflag當(dāng)前指向的元素
* */
if(array[left]==array[r]) {
temp=array[left];
array[left]=array[lflag];
array[lflag]=temp;
lflag++;
}
left++;
}
while(array[right]>=array[r] && right>=l) {
/**
* 如果array[right]與pivot相等勘伺，則將其交換到
* rflag當(dāng)前指向的元素
* */
if(array[right]==array[r]) {
temp=array[right];
array[right]=array[rflag];
array[rflag]=temp;
rflag--;
}
right--;
}
if(left>=right) break;
/**
* 將左邊大于pivot的元素與右邊小于pivot的元素進(jìn)行
* 交換
* */
temp=array[left];
array[left]=array[right];
array[right]=temp;
left++;right--;
}
/**
* 由于left和lflag指向的當(dāng)前元素都是即將需要處理的元素跪腹，
* 也就是當(dāng)處理結(jié)束之后，他們都需要左移一步才是已經(jīng)處理好的
* 元素飞醉； 將等于pivot的元素交換到中間
* */
lflag--;left--;
while(lflag>=l) {
temp=array[left];
array[left]=array[lflag];
array[lflag]=temp;
left--;lflag--;
}
/**
* 由于right和rflag指向的當(dāng)前元素都是即將需要處理的元素冲茸，
* 也就是當(dāng)處理結(jié)束之后，他們都需要右移一步才是已經(jīng)處理好的
* 元素缅帘；將等于pivot的元素交換到中間
* 注意：由于pivot本身也需要移動(dòng)到中間轴术，所以這里的判斷條件
* 包含r
* */
rflag++;right++;
while(rflag<=r) {
temp=array[right];
array[right]=array[rflag];
array[rflag]=temp;
right++;rflag++;
}
/**
* 最終遞歸處理左右子序列部分
* */
quickSort_3(array, l, left);
quickSort_3(array, right, r);
}
int main() {
int array[]={2,5,8,2,1,6};
quickSort_3(array,0,5);
for(int i=0;i<6;i++)
printf("%d,",array[i]);
return 1;
}
存在問題：為什么要移動(dòng)相等的值，代碼未手動(dòng)實(shí)現(xiàn)
四钦无、優(yōu)化
使用插入排序
在子序列比較小的時(shí)候逗栽，其實(shí)插排是比較快的，因?yàn)閷?duì)于有序的序列失暂，插排可以達(dá)到O(n)的復(fù)雜度彼宠，如果序列比較小，則和大序列比起來會(huì)更加有序趣席，這時(shí)候使用插排效率要比快排高兵志。其實(shí)現(xiàn)方法也很簡(jiǎn)單：快排是在子序列元素個(gè)數(shù)變成1是，才停止遞歸宣肚，我們可以設(shè)置一個(gè)閾值n想罕，假設(shè)為5，則大于5個(gè)元素霉涨，子序列繼續(xù)遞歸按价，否則選用插排。（其實(shí)在C++的STL中笙瑟，歸并算法就是采用了這個(gè)思路楼镐，當(dāng)子序列小到一定程度的時(shí)候，直接選用插排對(duì)子序列進(jìn)行排序）
快排是在待排數(shù)列越趨近于有序時(shí)變得越慢往枷，復(fù)雜度越高框产，調(diào)用插排可以很好的解決這個(gè)問題凄杯。
