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

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

算法基礎—快速排序

• 前言
• 一、快速排序的時間復雜度
• 二、快速排序實現
• 總結
• 三、代碼

---

前言

---

快速排序就是先找一個關鍵字，然后通過一趟排序，把大于關鍵字的位于一側，小于關鍵字的位于一側，然后對兩側在進行排序。

一、快速排序的時間復雜度

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

二、快速排序實現

1.首先我們應該輸入數組的值

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快的，但是不要忘記用&符號。

2.確定函數的分界點
確定分界點之前，不要忘記考慮一種情況，左邊界==有邊界的時候，是不是應該直接退出函數？？

if (l >= r)
	{return;
	}

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

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

這個不加括號是因為?的優(yōu)先級要比>>的優(yōu)先級要高。
在這里我們以中間值為分界點，也可以選取q[0]當分解點。當然，最好選取中間值，當你選兩邊的值的時候，再做一些題的時候，可能會出現超時的情況。

這樣確定了分界點之后，就可以進行下一步了。

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

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呢？因為這里我用的是do—while循環(huán)，先執(zhí)行的i++，在執(zhí)行的判斷條件，大家也可以改成while循環(huán)。

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

就是這樣交換的，如果你的學的編程語言沒有swap這樣的函數，那么我們也可以自己實現一下

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

這個代碼夠簡單了，在這里不多說了。
4.最重要的一點，邊界問題

代碼如下（示例）：

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

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

總結

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

三、代碼

#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)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前文章：快速排序（分治）-創(chuàng)新互聯
鏈接分享：http://aaarwkj.com/article10/cogodo.html

成都網站建設公司_創(chuàng)新互聯，為您提供手機網站建設、動態(tài)網站、建站公司、Google、網站改版、虛擬主機

廣告

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