日常分享：歲聿云暮，日月其除，前路未遠(yuǎn)，步履不停。

為昭陽等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及昭陽網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、昭陽網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

算法基礎(chǔ)—快速排序

• 前言
• 一、快速排序的時(shí)間復(fù)雜度
• 二、快速排序?qū)崿F(xiàn)
• 總結(jié)
• 三、代碼

---

前言

---

快速排序就是先找一個(gè)關(guān)鍵字，然后通過一趟排序，把大于關(guān)鍵字的位于一側(cè)，小于關(guān)鍵字的位于一側(cè)，然后對(duì)兩側(cè)在進(jìn)行排序。

一、快速排序的時(shí)間復(fù)雜度

快速排序最優(yōu)情況下時(shí)間復(fù)雜度為：O( nlgn )
最優(yōu)情況下空間復(fù)雜度為： O(logn)
怎么去計(jì)算這個(gè)復(fù)雜度在這里就不多說了。

二、快速排序?qū)崿F(xiàn)

1.首先我們應(yīng)該輸入數(shù)組的值

const int N = 1e6 + 10;//1e6 就是1*10的6次方

int q[N];

int n;

	cin >>n;

	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

也可以用scanf，scanf和printf是要比cin，cout快的，但是不要忘記用&符號(hào)。

2.確定函數(shù)的分界點(diǎn)
確定分界點(diǎn)之前，不要忘記考慮一種情況，左邊界==有邊界的時(shí)候，是不是應(yīng)該直接退出函數(shù)？？

if (l >= r)
	{return;
	}

左邊界可不能>=有邊界。

int x = q[l + r >>1];

這個(gè)不加括號(hào)是因?yàn)?的優(yōu)先級(jí)要比>>的優(yōu)先級(jí)要高。
在這里我們以中間值為分界點(diǎn)，也可以選取q[0]當(dāng)分解點(diǎn)。當(dāng)然，最好選取中間值，當(dāng)你選兩邊的值的時(shí)候，再做一些題的時(shí)候，可能會(huì)出現(xiàn)超時(shí)的情況。

這樣確定了分界點(diǎn)之后，就可以進(jìn)行下一步了。

3.在這里有兩個(gè)指針，i和j，q[i]小于x,就++，直到出現(xiàn)大于x的情況，q[j]大于x，j就–，直到遇到小于x的情況。
代碼實(shí)現(xiàn)如下：

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

	while (i< j)
	{do
		{	i++;
		} while (q[i]< x);

		do
		{	j--;
		} while (q[j] >x);

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

這里為什么要用l-1和r+1呢？因?yàn)檫@里我用的是do—while循環(huán)，先執(zhí)行的i++，在執(zhí)行的判斷條件，大家也可以改成while循環(huán)。

可以把數(shù)組以中間值，分開，然后每個(gè)指針進(jìn)行移動(dòng)＋判斷，直到兩個(gè)指針都不滿足循環(huán)條件，進(jìn)入交換。

就是這樣交換的，如果你的學(xué)的編程語言沒有swap這樣的函數(shù)，那么我們也可以自己實(shí)現(xiàn)一下

if (i< j)
{int tmp = q[i];
	q[i] = q[j];
	q[j] = tmp;
}

這個(gè)代碼夠簡(jiǎn)單了，在這里不多說了。
4.最重要的一點(diǎn)，邊界問題

代碼如下（示例）：

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

也可以用其他方法，在這里就不多介紹了。

總結(jié)

為什么要學(xué)快速排序呢，明明有庫(kù)函數(shù)，如C++（sort），C語言（qsort）等等，
學(xué)快排，學(xué)的是思想，正如一句話：算法學(xué)的好，工作不愁找。哈哈

三、代碼

#includeusing namespace std;

const int N = 1e6 + 10;

int q[N];

int n;

void QuickSort(int q[], int l, int r)
{if (l >= r)
	{return;
	}

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

	while (i< j)
	{do
		{	i++;
		} while (q[i]< x);

		do
		{	j--;
		} while (q[j] >x);

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

		if (i< j)
		{	int tmp = q[i];
			q[i] = q[j];
			q[j] = tmp;
		}
	}

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

}

int main()
{cin >>n;

	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

	QuickSort(q, 0, n - 1);

	for (int i = 0; i< n; i++)
	{cout<< q[i]<< ' ';
	}

	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：快速排序（分治）-創(chuàng)新互聯(lián)
鏈接分享：http://chinadenli.net/article10/cogodo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、建站公司、Google、網(wǎng)站改版、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)