快速排序quicksort_快速排序的原理

快速排序quicksort_快速排序的原理一、简介快速排序是(Quicksort)是对冒泡排序的一种改进,是非常重要且应用比较广泛的一种高效率排序算法。二、算法思路快速排序是通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。大致步骤如下:首先设置一个分界值也就是基准值又是也称为监视哨,通过该分界值将数据分割成两部分。将大于或等于分界值的数据集中到右边,小于分界值的数据集中到左边。一趟排序过后,左边部

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、简介

快速排序是(Quick sort)是对冒泡排序的一种改进,是非常重要且应用比较广泛的一种高效率排序算法。


二、算法思路

快速排序是通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。

大致步骤如下:

  1. 首先设置一个分界值也就是基准值又是也称为监视哨,通过该分界值将数据分割成两部分。
  2. 将大于或等于分界值的数据集中到右边,小于分界值的数据集中到左边。一趟排序过后,左边部分中各个数据元素都小于分界值,而右边部分中各数据元素都大于或等于分界值,且右边部分个数据元素皆大于左边所有数据元素。
  3. 然后,左边和右边的数据可以看成两组不同的部分,重复上述1和2步骤
    当左右两部分都有序时,整个数据就完成了排序。

三、算法步骤图解

首先设置三个参数,first指向区间左端,last指向区间右端,key为当前的分界值。
从待排序的数据元素中选取一个通常为第一个作为基准值元素(key)key=num[0],设置双指针first指向区间左端,last指向区间右端。
在这里插入图片描述

一、

key 首先与 num[last] 进行比较,如果 num[last]<key,则num[first]=num[last]将这个比key小的数放到左边去,如果num[last]>=key则- -last,再拿num[last]与key进行比较,直到num[last]<key交换元素为止。

在这里插入图片描述
二、
num[last]<key交换元素后,转向左边部分,用num[first]与key进行比较,如果num[first]<key,则++first,然后继续进行比较,直至num[first]>key,则将num[last]=num[first]。

在这里插入图片描述
在这里插入图片描述

三、
重复上述一二步骤
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
四、
第一趟排序结束,得到[2,11,15,20,9,5] 23 [56,45,35] 然后对左右子数列进行同样的操作。
2 [11,15,20,9,5] 23 [35,45] 56
2 [5,9] 11 [20,15] 23 35 45 56
2 5 9 11 15 20 23 35 45 56
完成从小到大的排序


四、算法性能分析

最好情况
每次数据元素都能平均的分成两个部分。得到一个完全二叉树。如果有n个数据元素,那么数的深度为在这里插入图片描述
时间复杂度为O(nlogn)

最坏情况
在最坏的情况下,这个数仅有右子树或左子树,比较次数为 (n-1)+(n-2) + (n-3) + … +1=n*(n-1)/2 ,因此时间复杂度为O(n^2),在待排序数据元素已经有序的情况下快速排序时间复杂度最高

空间复杂度为O(n)
快速排序是一种不稳定的排序算法,会改变数据元素的相对位置,也是内排序中平均效率最高的排序算法。


五、代码实现

C

void quick_sort(int *num,int l,int r){ 
   
	//如果小于等于1个数据元素·直接返回结束快排函数 r为数组元素总个数
	if(l+1>=r){ 
   
		return ;
	}
	int first=l,last=r-1,key=num[first];
	while(first<last){ 
   
		while(first<last&&num[last]>=key){ 
   
			--last;
		}
		//如果值小于 key分界值 交换 
		num[first]=num[last];
		while(first<last&&num[first]<key){ 
   
			++first;
		}
		//如果值大于key分界值 交换 
		num[last]=num[first];
	}
	num[first]=key;
	//递归左右部分进行快排 
	quick_sort(num,l,first);
	quick_sort(num,first+1,r);
}

Java

public static int[] quick_sort(int[] num, int l, int r){ 
   
//r为数组元素总个数,last下标等于r-1
        int first=l,last=r-1,key=num[first];
        while(first<last){ 
   
            while(first<last&&num[last]>=key){ 
   
                --last;
            }
            //如果值小于 key分界值 交换
            num[first]=num[last];
            while(first<last&&num[first]<key){ 
   
                ++first;
            }
            //如果值大于key分界值 交换
            num[last]=num[first];
        }
        num[first]=key;
        //递归左右部分进行快排
         if (first>l) { 
   
             num=quick_sort(num, l, first);
         }
        if (first+1<r){ 
   
            num=quick_sort(num,first+1,r);
        }
        return num;
    }

以上就是快速排序算法的介绍,如有问题,欢迎大家指正!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169880.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • C语言再学习 — 段错误(核心已转储)

    参看:Linux下的段错误产生的原因及调试方法参看:Linux环境下段错误的产生原因及调试方法小结参看:维基百科–Segmentationfault参看:LINUX内核段错误调试详细指南精品培训PPT讲义一、什么是段错误?一旦一个程序发生了越界访问,cpu就会产生相应的保护,于是segmentationfault就出现了,通过上面的解释,段错误应该就是访问了不可访问的内存,这个内存区要

  • Java教程,全套Java基础视频教程「建议收藏」

    Java教程,全套Java基础视频教程「建议收藏」深知广大爱好Java的人学习是多么困难,没视频没资源,上网花钱还老被骗。为此我呕心沥血整理了这套Java教程,不管你是不懂电脑的小白,还是已经步入开发的大牛,这套路线路你都值得拥有,小白看上面的视频可以成功学会Java并且顺利工作,大神看了上面的资源肯定会谆谆乐道,教程的宗旨就是分享,专业,便利,让喜爱Java的人,都能平等的学习。首先建立好开发环境非常重要,工欲善其事,必先利其器。做任何开发…

  • RelativeLayout.LayoutParams.addRule()方法

    RelativeLayout.LayoutParams.addRule()方法1、应用场景

  • Django(27)Django类视图添加装饰器[通俗易懂]

    Django(27)Django类视图添加装饰器[通俗易懂]类视图在写视图的时候,Django除了使用函数作为视图,也可以使用类作为视图。使用类视图可以使用类的一些特性,比如继承等。Viewdjango.views.generic.base.View是主

  • java书籍借阅系统_基于JAVA的图书借阅管理系统-.doc[通俗易懂]

    摘要各单位图书资料,传统的图书管理方已无法适应形势需,用计算机发图书资管理系统地查询、修改和维护相关信图书馆拥有丰富的文献信息资源,是社会信息系统的重要组成部分,在信息社会中的作用愈来愈重要。JAVA环境下连接数据库的并提取信息的一个管理信息系统的过程。通过对图书管理的调查和需求分析,创建了一套行之有效的计算机管理图书馆的方案。文章详细介绍了该系统的各个部分的功能,包括图书管理,学生管理,借阅…

  • inputstreamwriter_computrace

    inputstreamwriter_computrace关于往文件存入数据所使用的编码和解析时编码产生的问题解码的格式和编码的格式一定要相同否则会出现乱码importjava.io.*;publicclassFuXi3{publicstaticvoidmain(String[]args)throwsIOException{demo01();demo02();}privatestaticvoiddemo02()thro.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号