一、快速排序原理

快速排序（QuickSort）是一種基于分治法的高效排序算法。它的基本思想是通過(guò)一個(gè)稱為“基準(zhǔn)”（pivot）的元素將數(shù)組劃分為兩部分，一部分的所有元素都比基準(zhǔn)小，另一部分所有元素都比基準(zhǔn)大，然后遞歸地對(duì)這兩部分進(jìn)行同樣的操作，直到整個(gè)數(shù)組有序。 

二、快速排序標(biāo)準(zhǔn)代碼

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return; //遞歸停止條件
	int i = l - 1, j = r + 1, x = q[l + r >> 1]; //設(shè)定指針,基準(zhǔn)
	while (i < j)
	{
		do i++; while (q[i] < x); //q[i]大于等于基準(zhǔn)時(shí),指針i停止
		do j--; while (q[j] > x); //q[j]小于等于基準(zhǔn)時(shí),指針j停止
		if (i < j) swap(q[i], q[j]); //判斷是否i<j,交換i,j對(duì)應(yīng)的數(shù)組元素
	} // 結(jié)束時(shí)數(shù)組被分為 >=x,<=x 的兩部分
	quick_sort(q, l, j); //繼續(xù)分直到分到一到兩個(gè)元素此時(shí)數(shù)組有序
	quick_sort(q, j + 1, r);
}

三、代碼解析

我們以一個(gè)簡(jiǎn)單的例子幫助我們了解快速排序

1.排序的數(shù)組以及需要排序元素的范圍，無(wú)返回值

void quick_sort(int q[], int l, int r)

 2.遞歸結(jié)束的條件：元素剩一個(gè)或空

if (l >= r) return;

3.設(shè)定變量，其中 i, j 為兩個(gè)指針?lè)謩e減 1 加 1 是為了下一步的 do while 循環(huán)，x 即為“基準(zhǔn)”（pivot) 用來(lái)將列表分為 <=x 和 >=x 的兩部分，x 是隨機(jī)的，這里取了數(shù)組中間的一個(gè)元素，l + r >> 1相當(dāng)于 (l + r)/2 (pivot:q[2] = 4)向下取整(提高了效率)

int i = l - 1, j = r + 1, x = q[l + r >> 1];

	5	3	4	1	2
i	0	1	2	3	4	j

4.while循環(huán)實(shí)現(xiàn)了遍歷、比較、交換的功能，先使 i 指針遞增直到 i 所對(duì)應(yīng)的元素 >=x 停止,接下來(lái)使 j 指針遞減直到其對(duì)應(yīng)的元素 <=x 停止

while (i < j)
{
	do i++; while (q[i] < x);
	do j--; while (q[j] > x);
	if (i < j) swap(q[i], q[j]);
}

交換之后開(kāi)啟下一次循環(huán)

滿足 i<j 交換

不滿足 i<j 不交換,此時(shí)整個(gè) while 循環(huán)結(jié)束,注意此時(shí) j(包含)往左為 <=4 部分,j + 1 及其往右為 >=4部分 

5.接下來(lái)就是遞歸了,每次運(yùn)行分將數(shù)組為左<=右的兩部分,我們只需將左右兩部分分別執(zhí)行函數(shù)程序得到直到剩兩個(gè)或一個(gè)元素,此時(shí)數(shù)組便有序了

quick_sort(q, 0, 2); 

x(pivot)=3

quick_sort(q, 0, 1); 

x(pivot)=2

剩一個(gè)元素時(shí),執(zhí)行遞歸停止程序:

if (l >= r) return;

 數(shù)組中最初的“左”部分就變?yōu)?/p>

而最初的“右”部分:x(pivot)=4

if (i < j) swap(q[i], q[j]);

不滿足 if 條件以及 while 條件,while 循環(huán)停止,依舊選擇了 j 為分界點(diǎn)分到一個(gè)元素時(shí)結(jié)束遞歸

此時(shí)代碼全部有序

quick_sort(q, l, j); 
quick_sort(q, j + 1, r);

6.總結(jié)

快速排序利用兩個(gè)指針對(duì)數(shù)組的元素進(jìn)行比較交換進(jìn)行部分排序，再利用遞歸整體排序

四、使用while循環(huán)的快速排序

1.代碼

代碼1.由快排代碼等價(jià)轉(zhuǎn)化而來(lái)

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l, j = r, x = q[l + r >> 1];
    while (i < j)
    {
        while (q[i] < x) i++;
        while (q[j] > x) j--;
        if (i < j)
        {
            swap(q[i], q[j]);
            if (i + 1 < j - 1)
            {
                i++;
                j--;
            }
            else
            {
                i++;
                j--;
                while (q[i] < x) i++;
                while (q[j] > x) j--;
                break;
            }
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

代碼2.效率提高版

void quick_sort(int q[], int l, int r) {
	if (l >= r) return;
	int x = q[l + r >> 1];
	int i = l, j = r;
	while (i <= j) { // 注意：這里應(yīng)該是 i <= j 而不是 i < j
		while (q[i] < x) i++;
		while (q[j] > x) j--;
		if (i <= j) {
			swap(q[i], q[j]);
			i++;
			j--;
		}
	}
	quick_sort(q, l, j);   
	quick_sort(q, i, r);   
}

2.代碼2解析

1.因?yàn)闆](méi)有 do 過(guò)程,所以指針起始位置直接設(shè)在了 0 和 -1 的位置,

if (l >= r) return;
int x = q[l + r >> 1];
int i = l, j = r;

5	3	4	1	2
i				j

2. while 循環(huán)中的 while 循環(huán)先判斷是否滿足條件,滿足的話指針加/減 1,這樣停止時(shí)依舊是對(duì)應(yīng)元素 >=x 或 <=x 時(shí)的指針,

while (i <= j) 
{ 
	while (q[i] < x) i++;
	while (q[j] > x) j--;
	if (i <= j)
    {
		swap(q[i], q[j]);
		i++;
		j--;
	}
}

換過(guò)之后+=或--

交換，++/--

不滿足 i<=j while 循環(huán)結(jié)束.

關(guān)于 i<=j 的條件判斷,我們給出新的案例

交換之后 ++/--

注意此時(shí)并沒(méi)有返回(return),

遞歸代碼:分別以 j 和 i 作為分界點(diǎn)

quick_sort(q, l, j);   
quick_sort(q, i, r);   

而如果條件判斷為 < 的話 i=j 時(shí)就會(huì)造成下一次遞歸多了一個(gè)元素,

而標(biāo)準(zhǔn)代碼的運(yùn)行過(guò)程到此處后結(jié)束,以 j 和 j+1 為分界點(diǎn)不會(huì)造成此問(wèn)題.

因此再進(jìn)行一次循環(huán)

而此時(shí)元素 2 的位置是 i,j同時(shí)停過(guò)的位置即為基準(zhǔn) x,而i,j也會(huì)再下一次++/--后停止,所以我們可以直接將元素 2 所對(duì)應(yīng)的數(shù)組位置固定不動(dòng),將元素 2 左右的數(shù)組遞歸處理. 

quick_sort(q, l, j);   
quick_sort(q, i, r);   

五、總結(jié)

使用 while 循環(huán)會(huì)比 do while 多一層內(nèi)層循環(huán),所以 do while 循環(huán)效率更高,建議只用 do while 循環(huán).

到此這篇關(guān)于C++快速排序的文章就介紹到這了,更多相關(guān)C++快速排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論