【算法导论】快速排序-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】快速排序

简介: 快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
+关注继续查看

快速排序

        快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。另外,它能够进行就地排序,因此在虚拟内存中也能较好的运行。

        快速排序算法的性能:其运行时间与划分是否对称有关,而是否对称与主元的选取有关。从渐进的意义上讲,如果对称,就和合并的算法一样快,如果不对称,就和插入排序算法一样慢。需要注意的是,但每次递归是都是按照常数比例划分时,从渐进意义上看,与对称划分效果一样,都是nlgn.

        和合并排序一样,快速排序也是基于分治模式的。分治过程分为三个步骤:分解、解决、合并。

        快速合并的基本思想:从要排序的序列中,随意取一个值作为主元,从而将序列以此分为大于和小于主元的两个子序列,然后重复上述过程(递归调用)。

下面以一个分解过程为例:

        假设要排序的序列为:2、8、7、1、3、5、6、4。首先,随便选取主元,在这里我们选择4;其次,通过分解将原序列分为子序列2、1、3和子序列7、5、6、8;最后分别以两个子序列为原序列,不断重复上述过程。分解过程的图解如下:



  具体实现如下:

  • 分解过程:
    /**************************************************\
    函数功能:将原数组分成全大于和全小于x的两个子数组
    输入:原始数组、要对数组进行操作的起始和结束下标
    输出:x在数组中的位置
    \**************************************************/
    
    int Partition(int*Array,int n,int p,int r)
    {
    	int x=Array[r];
    	int i=p-1;
    	int temp=0;
    	for(int j=p;j<=r-1;j++)
    	{
    		if(Array[j]<=x)
    		{
    			i++;
    			temp=Array[i];
    			Array[i]=Array[j];
    			Array[j]=temp;
    		}
    	}
    	temp=Array[i+1];
    	Array[i+1]=Array[r];
    	Array[r]=temp;
    
    	return i+1;
    }

  • 递归过程:

    /**************************************************\
    函数功能:递归调用分解函数,进行快速排序
    输入:原始数组、要对数组进行操作的起始和结束下标
    输出:无
    \**************************************************/
    
    void QuickSort(int* Array,int n,int p,int r)
    {
    	int q=0;
    	if(p<r)
    	{
    		q=Partition(Array,n,p,r);
    		QuickSort(Array,n,p,q-1);
    		QuickSort(Array,n,q+1,r);
    	}
    }


    完整实例:

    #include<stdio.h>
    
    int Partition(int*Array,int n,int p,int r);
    void QuickSort(int* Array,int n,int p,int r);
    
    void main()
    {
    	int Array[8]={2,8,7,1,3,5,6,4};
    	int n=sizeof(Array)/sizeof(int);
    	int p=0;
    	int r=n-1;
    	QuickSort(Array,n,p,r);
    
    	for(int k=0;k<n;k++)
    		printf("%d ",Array[k]);
    	printf("\n");
    }
    
    /**************************************************\
    函数功能:将原数组分成全大于和全小于x的两个子数组
    输入:原始数组、要对数组进行操作的起始和结束下标
    输出:x在数组中的位置
    \**************************************************/
    
    int Partition(int*Array,int n,int p,int r)
    {
    	int x=Array[r];
    	int i=p-1;
    	int temp=0;
    	for(int j=p;j<=r-1;j++)
    	{
    		if(Array[j]<=x)
    		{
    			i++;
    			temp=Array[i];
    			Array[i]=Array[j];
    			Array[j]=temp;
    		}
    	}
    	temp=Array[i+1];
    	Array[i+1]=Array[r];
    	Array[r]=temp;
    
    	return i+1;
    }
    
    /**************************************************\
    函数功能:递归调用分解函数,进行快速排序
    输入:原始数组、要对数组进行操作的起始和结束下标
    输出:无
    \**************************************************/
    
    void QuickSort(int* Array,int n,int p,int r)
    {
    	int q=0;
    	if(p<r)
    	{
    		q=Partition(Array,n,p,r);
    		QuickSort(Array,n,p,q-1);
    		QuickSort(Array,n,q+1,r);
    	}
    }

    注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

    #include<stdio.h>
    void main()
    {
    int i=0;
    for(int i=0;i<5;i++)
    printf("%d ",i);
    }

    则在VC 6.0上需改为:

    #include<stdio.h>
    void main()
    {
    int i=0;
    for(i=0;i<5;i++)
    printf("%d ",i);
    } 



    原文:http://blog.csdn.net/tengweitw/article/details/9627659

    作者:nineheadedbird


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10466 0
算法笔记--快速排序
快速排序是交换排序的一种,算法效率高,需要额外的辅助空间 1. 算法思想           从待排序序列中选取一个元素,以其值作为中间值,把比其小的元素放到左边,比起大的元素放到右边;然后递归地对左、右部分排序,直至每一部分元素个数为1,整个序列有序。
635 0
算法笔记--基数排序
基数排序是一种数据格式相关的算法,适用范围有限,当数据位数较小时,基数排序法的时间复杂度近似为O(n),效率高于其它的稳定性排序算法。 1. 算法思想           以十进制数为例,现将元素按个位出入一次基数桶,再按十位出入基数桶……直至按最高位出入基数桶,此时序列整体有序。
662 0
【算法导论】快速排序
快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
823 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
12281 0
【算法导论】计数排序
计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
897 0
【算法导论】插入排序法
插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.
897 0
图解排序算法之快速排序-单端探测法
原文转载:https://www.cnblogs.com/MOBIN/p/4681369.html
3503 0
【算法导论】基数排序
基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
801 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载