快捷導(dǎo)航

超詳細(xì)解析C++實(shí)現(xiàn)快速排序算法的方法

更新時(shí)間：2022年09月22日 11:27:35 作者：sunny-ll

快速排序是比較快的排序方法。它的基本思想是通過(guò)一組排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，本文將用C++實(shí)現(xiàn)快速排序算法，需要的可以參考一下

一、前言

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.問題分析

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

①：取第一個(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;
}