快速排序法怎么排(计算机入门必备算法——快速排序法)
1、引言
今天的运气不是很好,再加上项目的压力。准备停止学习一周,等把项目这一关过了,再继续深入学习分享算法。后来吧今天遇到的事情都比较郁闷,也无心情继续开发项目。便想转移一下注意力,继续学习快速排序算法的内容。
昨天了解了递归的使用原理。今天可以使用这个新技能来解决一个新的问题————快速排序。快速排序是一种排序算法,这个算法比前天学习的选择排序要快得多,实属优雅代码的典范。
2、快速排序
2.1 学习准备
这里讲解一个比较著名的递归式问题解决方法————分而治之(divide and comquer,D&C)。为了方便理解,还是使用一个示例给大家讲解一下这是个什么样的使用原理。
给定一个数字数组arr=[2,4,6],我们可以将这些数字相加并返回结果,使用循环其实可以很容易得出结论(具体代码可以自行来敲哦!可以粘到留言板我帮你检查哦~),那么如何使用递归函数解决这个需求呢?
这里给出一种思路实现:
1、找出基线条件
我们首先考虑最简单的数组是什么样的?一种是空数组或者数组中只有一个元素,这完全可以直接计算出来,结果要么就是null或者就是这个元素的值。计算总和非常容易,这就是我们需要找的基线条件(不明白基线条件可以看昨天的文章哦)。
2、缩小数组
我们需要算出这个数组的和,其实可以表示为sum([2,4,6]),那么如何缩小数组的规模呢?那么sum([2,4,6])=2+sum([4,6]) = 2 + 4 + sum([6])(达到基线条件) = 2+4+6=12。
3、函数的运行过程
下图解释了函数是如何运行的,递归保存了运行的状态!
运行过程
运行状态
2.2 快速排序的原理
使用快速排序算法对数组进行排序,首先考虑对于排序算法而言,最简单的数组上面介绍要么是空数组或者只有一个元素的数组。因此基线条件为空或者只包含一个元素。在这种情况,可以直接返回该数组。
代码片段实现:
private int[] quickSort(int[] array){
if(array.length < 2){
return array;
}
}
我们再在数组里加一个元素,两个元素应该如何排序呢?思路也很简单,如果从小到大排序,就需要将这两个元素进行比较,如果前一个比较小,直接返回;如果前一个比较大,就需要互相交换,然后返回数组。那么包含三个元素或者更长的数组应该怎么排序呢?
此时我们可以考虑分而治之算法,将数组进行分解,直到满足基线条件。第一步,从数组中选择一个基准值,理论上这个基准值是可以随意挑选的,你可以选择数组首项也可以选择中项甚至可选择尾项。(有什么区别在后面讲)
我们暂时先将数组中的第一个值用作基准值,接下来,我们需要找出比基准值大的和小的元素,这被称为"分区",这样操作之后,你会有一个比基准值小的数字组成的子数组、基准值、一个比基准值大的数字组成的子数组。
但是这里只是进行了分区,但这个分区数组并不一定就是有序的。但是我们三项的数组就可以在选出一个基准值的情况下,然后对后面的数组(只含有两项)进行排序(这个很容易),这样我们也得到了有序数组,那么四项数组、五项数组甚至更多项呢?
2.2 代码实现
书上使用的python代码,我将其翻译为java语言,快速排序算法利用python语言是很好实现的,但是java实现起来还是比较麻烦的。通过网上查阅,先将编译好的java代码进行展现。
private static int partition(int[] arr, int low, int high) {
//指定左指针i和右指针j
int i = low;
int j= high;
//将第一个数作为基准值。挖坑
int x = arr[low];
//使用循环实现分区操作
while(i<j){//5 8
//1.从右向左移动j,找到第一个小于基准值的值 arr[j]
while(arr[j]>=x && i<j){
j--;
}
//2.将右侧找到小于基准数的值加入到左边的(坑)位置, 左指针想中间移动一个位置i++
if(i<j){
arr[i] = arr[j];
i++;
}
//3.从左向右移动i,找到第一个大于等于基准值的值 arr[i]
while(arr[i]<x && i<j){
i++;
}
//4.将左侧找到的打印等于基准值的值加入到右边的坑中,右指针向中间移动一个位置 j--
if(i<j){
arr[j] = arr[i];
j--;
}
}
//使用基准值填坑,这就是基准值的最终位置
arr[i] = x;//arr[j] = y;
//返回基准值的位置索引
return i; //return j;
}
private static void quickSort(int[] arr, int low, int high) {//???递归何时结束
if(low < high){
//分区操作,将一个数组分成两个分区,返回分区界限索引
int index = partition(arr,low,high);
//对左分区进行快排
quickSort(arr,low,index-1);
//对右分区进行快排
quickSort(arr,index+1,high);
}
}
2.3 运行时间
快速排序的运行时间在于你选择的基准值。假设你一直都选择第一个元素作为基准值,且要处理的数组是有序的。快速排序不检查数组元素的顺序,因此还是会尝试对其排序,但是这会有一个问题,每次选择第一个作为基准值,导致比基准值小的数组都是空的,使得调用栈非常高。运行时间较长。栈长表示为O(n)。
调用栈(最糟情况)
那有没有更好的办法呢?有的,我们可以参考二分查找的实现方法,每次选择中间的元素作为基准值,就会发现调用栈被减短了许多,不需要太多的递归调用,就会达到基线条件,最佳情况下栈长为O(logn)。
最佳情况
因此,在最糟糕的情况下(选择第一个为基准值)运行时间为O(n)。在最佳情况下,运行时间仅为O(nlogn)。
-
乒乓球能够成为中国国球,有以下几个原因:乒乓球的群众基础非常广泛。乒乓球是一项简单易学、趣味性强、老少皆宜的运动,无论是在学校、公园、街头巷尾还是体育馆、健身房,都能看到乒乓球爱好者的身影。这也使得乒乓球成为了中国最受欢迎的体育项目之一。乒乓球的技术要求相对较低,容易上手。相比其他球类项目,乒乓球的[详细]
-
区分羊是公是母,很多人都会按照羊的角来判断,大众也都会觉得公羊有角,母羊没有角,那么这样区分到底对不对?其实这种想法是错误的,公羊和母羊有没有角,不是根据性别决定的,而是要看种类。1.山羊大部分山羊都是有角的,不过公羊和母羊的角长得不一样。山羊的角又长又尖,会向后或者是朝下弯曲,而母山羊的角则比较细[详细]
-
鱤鮈鱲鯮鮍鯝鲌,鱊鲃䱻鳤鮠鮡鮀,它们的拼音分别为:gǎn,jū ,liè ,zōng,pí, gù,bó,yù, bā,huá,guǎn ,wéi,zhào, tuó。其中比较常见的,比如说鱤鱼,之前我的文章中也有过介绍,此字念感。还有就是宽鳍鱲、长鳍鱲、斑鳍鱲之类的,这些原生鱼经常出现在我们的溪流[详细]
-
窗帘在每家每户都有使用,因为窗帘的作用实在太大了额,它不仅装饰点缀了我们的家庭环境,而且还保护了我们的隐私,调节了家里的光线,但在美丽的窗帘背后,却往往最容易被大家所忽略来清洁它。相信有的家庭可能从安装上去还没有清洗过。其实这种做法是错误的,因为窗帘离窗户最近,为我们挡住的都是外界的灰尘还有细菌,所[详细]
-
构图是设计师为了表现一定的思想、意境、情感,在一定范围内,运用审美原则,对各种形象或符号进行的合理安排。平面构图包括3个方面的构成要素,下面将逐一对这3个要素进行介绍。内容要素包括文字、插图、标志,在其转化成画面的过程中,必须将文字、插图、标志等转化为点、线、面等,并遵循平面构成的原理。同时,在转化[详细]