目錄

一、前言

（1）分治算法

（2）分治算法解題方法

? ? 1.分解：

? ? 2.治理：

? ? 3.合并：

二、快速排序

1.問題分析

2.算法設(shè)計(jì)

? ? （1）分解：

? ? （2）治理 ：

? ? （3）合并：

? ? （4）基準(zhǔn)元素的選?。?/p>

3.算法分析

三、AC代碼

?四、共勉

一、前言

（1）分治算法

? ? 快速排序，其實(shí)是一種分治算法，那么在了解快速排序之前，我們先來(lái)看看什么是分治算法。在算法設(shè)計(jì)中，我們引入分而治之的策略，稱為分治算法，其本質(zhì)就是將一個(gè)大規(guī)模的問題分解為若干個(gè)規(guī)模較小的相同子問題，分而治之。

（2）分治算法解題方法

? ? 1.分解：

? ? 將要解決的問題分解為若干個(gè)規(guī)模較小、相互獨(dú)立、與原問題形式相同的子問題。

? ? 2.治理：

? ? 求解各個(gè)子問題。由于各個(gè)子問題與原問題形式相同，只是規(guī)模較小而已，而當(dāng)子問題劃分得足夠小時(shí)，就可以用簡(jiǎn)單的方法解決。

? ? 3.合并：

? ? 按原問題的要求，將子問題的解逐層合并構(gòu)成原問題的解。

二、快速排序

1.問題分析

? ? 快速排序是比較快的排序方法。它的基本思想是通過一組排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此使所有數(shù)據(jù)變成有序序列。

2.算法設(shè)計(jì)

? ? （1）分解：

? ??先從數(shù)列中取出一個(gè)元素作為基準(zhǔn)元素。一基準(zhǔn)元素為標(biāo)準(zhǔn)，將問題分解為兩個(gè)子序列，使小于或者等于基準(zhǔn)元素的子序列在左側(cè)，使大于基準(zhǔn)元素的子序列在右側(cè)。

? ? （2）治理 ：

? ??對(duì)兩個(gè)子序列進(jìn)行快速排序（遞歸快速排序）。

? ? （3）合并：

? ? 將排好的兩個(gè)子序列合并在一起，得到原問題的解。

? ? （4）基準(zhǔn)元素的選?。?/h4>

? ? ①：取第一個(gè)元素。(通常選取第一個(gè)元素)

? ? ②：取最后一個(gè)元素

? ? ③：取中間位置的元素

? ? ④：取第一個(gè)、最后一個(gè)、中間位置元素三者之中位數(shù)

? ? ⑤：取第一個(gè)和最后一個(gè)之間位置的隨機(jī)數(shù) k (low<=k<=hight)

3.算法分析

? ? 假設(shè)當(dāng)前的待排序的序列為 R[low,hight] ，?其中 low<=hight。同時(shí)選取首元素為基準(zhǔn)元素。

步驟一：選取首元素的第一個(gè)元素作為基準(zhǔn)元素? pivot=R[low] ，i=low ，j=hight。

步驟二：從右向左掃描，找到小于等于 pivot 的數(shù)，如果找到，R[i] 和 R[j] 交換 ，i++。

步驟三：從左向右掃描，找到大于 pivot 的數(shù)，如果找到，R[i] 和 R[j] 交換，j--。

步驟四：重復(fù) 步驟二~步驟三，直到? j 與?i 的指針重合 返回位置 mid=i ，該位置的數(shù)正好是 pivot 元素。

? ? 至此換成一趟排序，此時(shí)以 mid 為界線，將數(shù)據(jù)分割為兩個(gè)子序列，左側(cè)子序列都比 pivot 數(shù)小，右側(cè)子序列都比 pivot 數(shù)大，然后再分別對(duì)這兩個(gè)子序列進(jìn)行快速排序。??

? ? 下面我將以序列（30，24，5，58，18，36，12，42，39）為例，進(jìn)行圖解。

（1）初始化。i=low ，j=hight，pivot=R[low]=30。如下圖所示：

?（2）向左走，從數(shù)組的右邊位置向左找，一直找到小于等于 pivot 的數(shù)，找到R[j]=12，R[i]與R[j]交換，i++。如下圖所示：

?

（3）向右走，從數(shù)組的左邊位置向右找，一直找到比 pivot 大的數(shù)，找到 R[i]=58 ,R[i] 與 R[j] 交換?，j--。

?（4）向左走，從數(shù)組的右邊位置向左找，一直找到小于等于 pivot 的數(shù)，找到R[j]=18，R[i]與R[j]交換，i++。如下圖所示：

?

?（5）向右走，從數(shù)組的左邊位置向右找，一直找到比 pivot 大的數(shù)，這是 i=j，第一輪排序結(jié)束，返回 i 的位置，mid=i 。以上的操作是對(duì)序列進(jìn)行分解，其代碼如下圖所示：

int part(int* r, int low, int hight)  //劃分函數(shù)
{
	int i = low, j = hight, pivot = r[low]; //基準(zhǔn)元素
	while (i < j)
	{
		while (i<j && r[j]>pivot) //從右向左開始找一個(gè) 小于等于 pivot的數(shù)值
		{
			j--;
		}
		if (i < j)
		{
			swap(r[i++], r[j]);  //r[i]和r[j]交換后 i 向右移動(dòng)一位
		}
		while (i < j && r[i] <= pivot) //從左向右開始找一個(gè) 大于 pivot的數(shù)值
		{
			i++;
		}
		if (i < j)
		{
			swap(r[i], r[j--]);  //r[i]和r[j]交換后 i 向左移動(dòng)一位
		}
	}
	return i;  //返回最終劃分完成后基準(zhǔn)元素所在的位置
}

（6）然后在分別對(duì)這兩個(gè)序列（12，24，5，18）和（36，58，42，39）進(jìn)行快速排序（遞歸）。其代碼如下圖所示：

void Quicksort(int* r, int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = part(r, low, hight);  // 返回基準(zhǔn)元素位置
		Quicksort(r, low, mid - 1); // 左區(qū)間遞歸快速排序
		Quicksort(r, mid+1, hight); // 右區(qū)間遞歸快速排序
	}
}

三、AC代碼

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int part(int* r, int low, int hight)  //劃分函數(shù)
{
	int i = low, j = hight, pivot = r[low]; //基準(zhǔn)元素
	while (i < j)
	{
		while (i<j && r[j]>pivot) //從右向左開始找一個(gè) 小于等于 pivot的數(shù)值
		{
			j--;
		}
		if (i < j)
		{
			swap(r[i++], r[j]);  //r[i]和r[j]交換后 i 向右移動(dòng)一位
		}
		while (i < j && r[i] <= pivot) //從左向右開始找一個(gè) 大于 pivot的數(shù)值
		{
			i++;
		}
		if (i < j)
		{
			swap(r[i], r[j--]);  //r[i]和r[j]交換后 i 向左移動(dòng)一位
		}
	}
	return i;  //返回最終劃分完成后基準(zhǔn)元素所在的位置
}
void Quicksort(int* r, int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = part(r, low, hight);  // 返回基準(zhǔn)元素位置
		Quicksort(r, low, mid - 1); // 左區(qū)間遞歸快速排序
		Quicksort(r, mid+1, hight); // 右區(qū)間遞歸快速排序
	}
}
int main()
{
	int a[10001];
	int  N;
	cout << "請(qǐng)輸入要排序的數(shù)據(jù)的個(gè)數(shù)： " << endl;
	cin >> N;
	cout << "請(qǐng)輸入要排序的數(shù)據(jù)： " << endl;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	cout << endl;
	Quicksort(a, 0, N - 1);
	cout << "排序后的序列為： " << endl;
	for (int i = 0; i < N; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

?四、共勉

? ? 以下就是我對(duì)分治：快速排序的理解，如果有不懂和發(fā)現(xiàn)問題的小伙伴，請(qǐng)?jiān)谠u(píng)論區(qū)說(shuō)出來(lái)哦，同時(shí)我還會(huì)繼續(xù)更新對(duì)分治算法的理解，請(qǐng)持續(xù)關(guān)注我哦?。。。。。。?！

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-778741.html

到了這里，關(guān)于快速排序算法C++實(shí)現(xiàn)（超詳細(xì)解析?。。。。┑奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！