分治算法----快速排序

骑猪看日落 2022-07-31 10:21 203阅读 0赞

一.算法思想:

假设要对某数组进行由小->大排序

(1) 分解: 对于乱序数组a\[R\](存取范围\[0->R\],有R+1个数),取一个基准元素a\[P\](一般以第一个数即a\[0\]为基准),确定某个Partition(位置)Q ,使a\[Q\]右边的数都大于等于a\[P\],a\[Q\]左边的数都小于等于a\[P\].

(2)递归分治:分解之后,数组变成3部分 a\[0\]-a\[Q\],a\[Q\],a\[Q+1\]-a\[R\]. a\[Q\]只有一个元素,以它为标杆,对a\[0\]->a\[Q\]和a\[Q+1\]->a\[R\]分别执行步骤(1)

二.例子示例:

数    组: 0  1  2 3 4 5 6

原序列: 7 12 9 8 5 2 3

⑴.令P=0,取标杆a\[P\]为7作为基准,把a\[0\]存起来,记x=a\[0\];

令i=P+1,i开始向右边走,找到>=7的数,此时i停留在下标1处

令j=R,j开始向左移动,找到<=7的数,则j停留在下标6处,如果i<j,交换a\[i\],a\[j\];

数    组: 0 1 2 3 4 5 6

现序列: 7 3 9 8 5 212

继续执行步骤⑴,i到下标2处,j到下标5处,如果i<j,交换a\[i\],a\[j\]

数    组: 0 1 2 3 4 5 6  
现序列: 7 3 2 8 5  9 12

继续执行步骤⑴,i到下标3处,j到下标4处,如果i<j,交换a\[i\],a\[j\]

数    组: 0 1 2 3 4 5 6

现序列: 7 3 2 5 8 9 12

其中,i,j的移动在循环中(见后续代码),如果找不到符合条件的数,会一直移动,直到i=r,则数组遍历完毕,i不再移动,此时i到了下标6处

而j继续移动,5符合条件,来到下标3处 ,但由于i>=j条件不成立,不交换a\[i\],a\[j\],此时交换a\[P\],a\[j\],j=3

数    组: 0 1 2 3 4 5 6

现序列: 5 3 2 7 8 9 12

到此一个小分割就结束了,返回j下标Q=3,可以看出a\[0->(j-1)\]都小于或等于标杆x,即7,a\[j+1->R\]都大于或等于x.

后续可按上续步骤执行,

a\[0\]-a\[Q\]:

数    组: 0 1 2

现序列: 5 3 2

x=0,i向右走,i=1,直到i=2,j向左找,找到a\[j\]<=x停止,此时j在下标2处,但由于i<j条件不成立,不交换a\[i\],a\[j\],此时交换a\[P\],a\[j\],则

数    组: 0 1 2

现序列: 2 3 5

a\[Q+1\]-a\[R\]:

数    组: 3 4 5 6

现序列: 7 8 9 12

同理,由于一直不满足条件,i走到下标6处 j走到下标3处,此时i>j,执行交换a\[P\],a\[j\],原序列不变,算法结束

所以最终序列为:

数    组: 0 1 2 3 4 5 6

现序列: 2 3 5 7 8 9 12

三.源代码:

#include<iostream>
    using namespace std;
    int Partition(int a[],int P, int R);
    void Quicksort(int a[],int P, int R)
    {
    	if(P<R)
    	{
    		int Q = Partition(a,P,R);
    		Quicksort(a,P,Q-1);
    		Quicksort(a,Q+1,R);
    	}
    }
    int Partition(int a[], int P, int R)
    {
    	int i=P,j=R+1;//由于i,j先移动 提前加一位,但是以a[0]为标杆,a[0]不参与比较,i不用先减1,可见★代码处
    	int x=a[P];
    	while(true){
    		while(a[++i]<x&&i<R);	//★  ++在前,先移动i再比较,所以初始i=P 此处目的是把i移动到a[i]>=x处或者i到最后一位停止.
    		while(a[--j]>x);		//把i移动到a[i]<=x处
    		if(i>=j) break;			//当i>=j大小标杆划分完成
    		swap(a[i],a[j]);	
    	}
    	swap(a[P],a[j]);			
    	return j;					//返回分界标杆
    }
    
    void main()
    {
    	int a[7]= {7,12,9,8,5,2,3};
    	cout<<"原序列:\n";
    	for (int i = 0; i < 7; i++)
    	{
    		cout<<a[i]<<" ";
    	}
    	Quicksort(a,0,6);		//此处传第三个参注意为n-1,n为待排序数个数,因为下标从0开始
    	cout<<"\n现序列:\n";
    	for (int i = 0; i < 7; i++)
    	{
    		cout<<a[i]<<" ";
    	}
    }

四.运行结果:

![20151227211837865][]

参考资料:《计算机算法设计与分析》 p25

五.时间复杂度:

快速排序每次将待排序数组分为两个部分,如果理想,每一次都将待排序数组划分成等长两个部分,则需要logn次划分。

平均需要(nlogn)

[20151227211837865]: /images/20220731/5e6f67e56fd145979e73fefb0e3affd0.png