快速排序

今天介绍快速排序,这也是在实际中最常用的一种排序算法,速度快,效率高。就像名字一样,快速排序是最优秀的一种排序算法。

思想

快速排序采用的思想是分治思想。

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的 元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

举例说明一下吧,这个可能不是太好理解。假设要排序的序列为

2 2 4 9 3 6 7 1 5 首先用2当作基准,使用i j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。首先比较2和5,5比2大,j左移

2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置

2 1 4 9 3 6 7 1 5 比较2和4,4大于2,因此将4移动到后面

2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变

经过第一轮的快速排序,元素变为下面的样子

[1] 2 [9 3 6 7 4 5]

之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。

代码

int quicksort(vector<int> &v, int left, int right){
        if(left < right){

                int key = v[left];
                int low = left;
                int high = right;

                while(low < high){
                        while(low < high && v[high] > key){
                                high--;
                        }

                        v[low] = v[high];

                        while(low < high && v[low] < key){
                                low++;
                        }

                        v[high] = v[low]

                }

                v[low] = key;
                quicksort(v,left,low-1);
                quicksort(v,low+1,right);

        }
}

分析

快速排序的时间主要耗费在划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n*n)

在最好情况下,每次划分所取的基准都是当前无序区的"中值"记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数:O(nlgn)

尽管快速排序的最坏时间为O(n2),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快者,快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。

一趟快速排序的算法是

   1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;

   2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

   3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;

   4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;

   5)、重复第3、4步,直到I=J;

   例如:待排序的数组A的值分别是:(初始关键数据X:=49)

                   A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]:

49        38       65       97       76       13        27

进行第一次交换后:   27        38       65       97       76       13        49

                   ( 按照算法的第三步从后面开始找

进行第二次交换后:   27        38       49       97       76       13        65

                  ( 按照算法的第四步从前面开始找>X的值,65>49,两者交换,此时I:=3 )

进行第三次交换后:   27        38       13       97       76       49        65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后:   27        38       13       49       76       97        65

( 按照算法的第四步从前面开始找大于X的值,97>49,两者交换,此时J:=4 )

      此时再执行第三不的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:27        38       13       49       76       97        65,即所以大于49的数全部在49的后面,所以小于49的数全部在49的前面。

快速排序法”使用的是递归原理,下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组 {53,12,98,63,18,72,80,46, 32,21},先找到第一个数--53,把它作为中间值,也就是说,要把53放在一个位置,使得它左边的值比它小,右边的值比它大。{21,12,32, 46,18,53,80,72,63,98},这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组,而这两个数组继续用同样 的方式继续下去,一直到顺序完全正确。      我这样讲你们是不是很胡涂,不要紧,我下面给出实现的两个函数:

/*
n就是需要排序的数组,left和right是你需要排序的左界和右界,
如果要排序上面那个数组,那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {
     /*
     这就是下面要讲到的函数,按照上面所说的,就是把所有小于53的数放
     到它的左边,大的放在右边,然后返回53在整理过的数组中的位置。
     */
     dp=partition(n,left,right);

     quicksort(n,left,dp-1);

     quicksort(n,dp+1,right); //这两个就是递归调用,分别整理53左边的数组和右边的数组
	}
}

我们上面提到先定位第一个数,然后整理这个数组,把比这个数小的放到它的左边,大的放右边,然后返回这中间值的位置,下面这函数就是做这个的。

int partition(int n[],int left,int right)
{
	int lo,hi,pivot,t;

	pivot=n[left];
	lo=left-1;
	hi=right+1;

	while(lo+1!=hi) {
		if(n[lo+1]<=pivot)
			lo++;
		else if(n[hi-1]>pivot)
			 hi--;
		else {
			t=n[lo+1];
			n[++lo]=n[hi-1];
			n[--hi]=t;
		}
	}

	n[left]=n[lo];
	n[lo]=pivot;
	return lo;
}

这段程序并不难,应该很好看懂,我把过程大致讲一下,首先你的脑子里先浮现一个数组和三个指针,第一个指针称为p指针,在整个过程结束之前它牢牢的指向第一个数,第二个指针和第三个指针分别为lo指针和hi指针,分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近,在逼近的过程中不停的与p指针的值比较,如果lo指针的值比p指针的值小,lo++,还小还++,再小再++,直到碰到一个大于p指针的值,这时视线转移到hi指针,如果 hi指针的值比p指针的值大,hi--,还大还--,再大再--,直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面,这时把p指针的值和碰面的值做一个调换,然后返回p指针新的位置。

#include<iostream>  
using namespace std;  

int a[200001],n;  
void swap(int &a,int &b)
{  
	int tmp = a;  
	a = b;  
	b = tmp;  
}  

int partition(int p,int r)
{  
	int rnd = rand()%(r-p+1)+p;  
	swap(a[rnd],a[r]);  
	int pvt = r, i = p-1;  
	for(int j = i+1;j<r;j++)  
	if(a[j]<a[pvt])  
	swap(a[j],a[++i]);  
	swap(a[++i],a[pvt]);  
	return i;  
}  


void qsort(int p,int r)
{  
	if(p<r){  
		int q = partition(p,r);  
		qsort(p,q-1);  
		qsort(q+1,r);  
	}  
}  

int main()
{  
	cin>>n;  
	for(int i=0;i<n;i++)  
	cin>>a[i];  
	qsort(0,n-1);  
	for( i=0;i<n;i++)  
	cout<<a[i]<<" ";  

	return 0;  
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

2762
来自专栏Crossin的编程教室

【Python 第72课】map 函数

来看两个问题: 1. 假设有一个数列,如何把其中每一个元素都翻倍? 2. 假设有两个数列,如何求和? 第一个问题,普通程序员大概会这么写: lst_1 = [...

31810
来自专栏aCloudDeveloper

VC库中快排函数的详解

Author: bakari  Date:  2012.8.9 以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写...

2237
来自专栏落影的专栏

程序员进阶之算法练习(三十四)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

1313
来自专栏风口上的猪的文章

.NET面试题系列[3] - C# 基础知识(1)

重要程度:10/10,身家性命般重要。通常这也是各种招聘工作的第一个要求,即“熟悉C#”的一部分。连这部分都不清楚的人,可以说根本不知道自己每天都在干什么。我们...

1902
来自专栏CDA数据分析师

Python迭代和迭代器详解

一个对象,物理或者虚拟存储的序列。list,tuple,strins,dicttionary,set以及生成器对象都是可迭代的,整型数是不可迭代的。如果你不确定...

2129
来自专栏极客慕白的成长之路

视觉直观感受 7 种常用的排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

844
来自专栏Python

迭代器和生成器

一 迭代和可迭代协议 什么叫迭代 1234不可以for循环,是因为它不可迭代。那么如果“可迭代”,就应该可以被for循环了。 这个我们知道呀,字符串、列表、元组...

22410
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:数组全解!!

正文之前 其实我的《C++ Primer》 已经看到第五章了,但是因为码字比较费时间,所以暂时没有迅速更新实在是对不住,但是没办法, 总不能一天拿出五六个小时来...

36010
来自专栏老马说编程

计算机程序的思维逻辑 (3) - 基本运算

运算 上节我们介绍了给数据赋值,有了初始值之后,可以对数据进行运算。计算机之所以称为"计算"机,是因为发明它的主要目的就是运算。运算有不同的类型,不同的数据类型...

1919

扫码关注云+社区

领取腾讯云代金券