日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

超詳細解析C++實現快速排序算法的方法_C 語言

作者：sunny-ll ? 更新時間： 2022-11-12 編程語言

一、前言

1.分治算法

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

2.分治算法解題方法

1.分解：

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

2.治理：

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

3.合并：

按原問題的要求，將子問題的解逐層合并構成原問題的解。

二、快速排序

1.問題分析

快速排序是比較快的排序方法。它的基本思想是通過一組排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據小，然后再按此方法對這兩部分數據進行快速排序，整個排序過程可以遞歸進行，以此使所有數據變成有序序列。

2.算法設計

（1）分解：

先從數列中取出一個元素作為基準元素。一基準元素為標準，將問題分解為兩個子序列，使小于或者等于基準元素的子序列在左側，使大于基準元素的子序列在右側。

（2）治理 ：

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

（3）合并：

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

（4）基準元素的選取：

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

②：取最后一個元素

③：取中間位置的元素

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

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

3.算法分析

假設當前的待排序的序列為 R[low,hight] ，?其中 low<=hight。同時選取首元素為基準元素。

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

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

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

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

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

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

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

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

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

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

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

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

（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);  // 返回基準元素位置
		Quicksort(r, low, mid - 1); // 左區間遞歸快速排序
		Quicksort(r, mid+1, hight); // 右區間遞歸快速排序
	}
}

三、AC代碼

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

原文鏈接：https://blog.csdn.net/weixin_45031801/article/details/126962679

欄目分類
最近更新