一、前言

1.分治算法

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

2.分治算法解題方法

1.分解：

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

2.治理：

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

3.合并：

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

二、快速排序

1.問題分析

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

2.算法設(shè)計

（1）分解：

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

（2）治理 ：

對兩個子序列進行快速排序（遞歸快速排序）。

（3）合并：

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

（4）基準(zhǔn)元素的選取：

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

②：取最后一個元素

③：取中間位置的元素

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

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

3.算法分析

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

步驟一：選取首元素的第一個元素作為基準(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 元素。

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

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

（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 。以上的操作是對序列進行分解，其代碼如下圖所示：

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

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

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) //從右向左開始找一個 小于等于 pivot的數(shù)值
        {
            j--;
        }
        if (i < j)
        {
            swap(r[i++], r[j]);  //r[i]和r[j]交換后 i 向右移動一位
        }
        while (i < j && r[i] <= pivot) //從左向右開始找一個 大于 pivot的數(shù)值
        {
            i++;
        }
        if (i < j)
        {
            swap(r[i], r[j--]);  //r[i]和r[j]交換后 i 向左移動一位
        }
    }
    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 << "請輸入要排序的數(shù)據(jù)的個數(shù)： " << endl;
    cin >> N;
    cout << "請輸入要排序的數(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;
}

到此這篇關(guān)于超詳細(xì)解析C++實現(xiàn)快速排序算法的方法的文章就介紹到這了,更多相關(guān)C++快速排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論