【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)

2019-12-17 - 快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)
【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)

单单看以上解释还是有些模糊,可以通过实例来理解它,下面通过一组数据来进行排序过程的解析:

花了点时间撸了下面这张快速排序示意图:

1)一开始选定数组的最后一个元素5作为基准值,也就是最终排序结果应该是以5为界限划分为左右两边。

【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)
【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)

2)从左边开始,寻找比5大的值,然后与5进行调换(因为如果比5小的值本来就应该排在5前面,比5大的值调换之后就去到了5的后面),一路过来找到了7,将7与5调换,结束此次遍历。

3)从右边开始,由于7已经是上一轮排好序的便不再动它,从10开始,一路向左遍历,寻找比5小的值,然后与5进行调换(因为如果比5大的值本来就应该排在5后面,比5小的值调换之后就去到了5的后前面),一路过来找到了4,将4与5调换,结束此次遍历。

【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)
【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)

4)从左边开始,由于3和4都是前两轮已经排好序的便不再动它,从2开始,一路向右遍历,寻找比5大的值,然后与5进行调换(道理同步骤2),一路过来找到了9,将9与5调换,结束此次遍历。

5)从右边开始,由于排在9后面的那几个数字都是上几轮排好序的便不再动它,从1开始,一路向右遍历,寻找比5小的值,然后与5进行调换(道理同步骤3),一下子就找到了1,将1与5调换,结束此次遍历。

【java快速排序算法】图文讲解 QuickSort 快速排序算法(Java版)

6)这个时候,发现5的左右两边都是排好序了的,所以结束此轮排序,5的左右两边抽出来各自进行下一轮的排序,规则同上,直到无法再拆分下去,即完成了整体的快速排序。

既然思路理清了,代码就容易上手了:

/** * 快速排序 * @author Android小Y */public class QuickSort { /** * 将数组的某一段元素进行划分,小的在左边,大的在右边 * @param a * @param start * @param end * @return */ public static int divide(int[] a, int start, int end){ //每次都以最右边的元素作为基准值 int base = a[end]; //start一旦等于end,就说明左右两个指针合并到了同一位置,可以结束此轮循环。

while(start < end){ while(start < end && a[start] <= base) //从左边开始遍历,如果比基准值小,就继续向右走 start ; //上面的while循环结束时,就说明当前的a[start]的值比基准值大,应与基准值进行交换 if(start < end){ //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后,此时的那个被调换的值也同时调到了正确的位置(基准值右边),因此右边也要同时向前移动一位 end--; } while(start < end && a[end] >= base) //从右边开始遍历,如果比基准值大,就继续向左走 end--; //上面的while循环结束时,就说明当前的a[end]的值比基准值小,应与基准值进行交换 if(start < end){ //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后,此时的那个被调换的值也同时调到了正确的位置(基准值左边),因此左边也要同时向后移动一位 start ; } } //这里返回start或者end皆可,此时的start和end都为基准值所在的位置 return end; } /** * 排序 * @param a * @param start * @param end */ public static void sort(int[] a, int start, int end){ if(start >= end){ //如果只有一个元素,就不用再排下去了 return; } else{ //如果不止一个元素,继续划分两边递归排序下去 int partition = divide(a, start, end); sort(a, start, partition-1); sort(a, partition 1, end); } } }

采用几组数据测试了下结果

public static void main(String[] args) { int[] a = new int[]{2,7,4,5,10,1,9,3,8,6}; int[] b = new int[]{1,2,3,4,5,6,7,8,9,10}; int[] c = new int[]{10,9,8,7,6,5,4,3,2,1}; int[] d = new int[]{1,10,2,9,3,2,4,7,5,6}; sort(a, 0, a.

length-1); System.out.println("排序后的结果:"); for(int x : a){ System.out.print(x " "); }}

快速排序最“快”的地方在于左右两边能够快速同时递归排序下去,所以最优的情况是基准值刚好取在无序区的中间,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数。此时的时间复杂度仅为O(NlogN)。

快速排序也有存在不足的情况,当每次划分基准值时,得到的基准值总是当前无序区域里最大或最小的那个元素,这种情况下基准值的一边为空,另一边则依然存在着很多元素(仅仅比排序前少了一个),此时时间复杂度为O(N*N)。

快速排序的速度快慢关键在于基准值的选取,它决定了划分次数以及比较次数,决定了快排的效率,因此,还有一些针对于基准值选取的优化方法,例如“三数据取中法”等,能够有效优化快速排序存在的不足之处。

如果将日常写代码比作拧螺丝,那数据结构和算法就好比一个扳手,单纯只是为了编码而编码,就好比徒手拧螺丝,有时候会特别吃力,而且拧完的效果也可能不佳,但如果借助扳手,就可以更高效精准地完成我们的工作。以上是本人对快速排序的一点浅见,如果觉得写得还不错的动动小手点个喜欢~~

相关阅读
快速排序算法动态图解 【快速排序算法动态图解】Java快速排序图文详解

有没有既不浪费空间又可以快一点的排序算法呢?那就是快速排序啦!光听这个名字是不是就觉得很高端。假设我们现在对6 1 2 7 9 3 4 5 10 8这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了。

java快速排序简单代码 【java快速排序简单代码】一种简单的用java实现快速排序(Quicksort)

1,快速排序(Quicksort)是对冒泡排序的一种改进。对数据量越大,数据分布越混乱的,一般认为是性能最好的。快排是分治思想的一种体现,把大的问题细化成小问题,把小问题细化成更小的问题,最终把问题缩小到一定规模内。

快速排序算法详细图解 【快速排序算法详细图解】排序算法(七)快速排序

1.算法思路 快速排序(QuickSort)是从冒泡排序演变而来及基于分而治之思想的排序算法。其效率比冒泡算法高得多,同冒泡排序一样,快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。

快速排序算法原理动画 【快速排序算法原理动画】快速排序算法(OC实现)

1.快速排序的意义 快速排序是一种优雅的排序算法,快速排序使用分而治之的策略。(一种递归式问题解决方法),快速排序是一种常用的排序算法,比起选择排序快的多,例如C语言标准库中的函数qsort实现的就是快速排序。

快速排序c语言实现 【快速排序c语言实现】C语言简单实现快速排序

快速排序是一种不稳定排序,它的时间复杂度为O(nlgn),最坏情况为O(n2)空间复杂度为O(nlgn)。 这种排序方式是对于冒泡排序的一种改进,它采用分治模式,将一趟排序的数据分割成独立的两部分。

推荐阅读
异食癖心理 【异食癖心理】印度26岁女子患有异食癖 吞下2.7斤珠宝与硬币
张朝阳是什么人 张朝阳是什么人 张朝阳:搜狐未“老”第四季度或实现盈利
美国大学申请 美国大学申请:招生官重视国际学生的哪些方面
马拉多纳电源 马拉多纳电源 马拉多纳为什么要戴两块表
20省份取消非农业户口 20省份取消非农业户口 30省份取消农业户口 农业户口和非农业户口区别
隔代遗传的病有哪些 隔代遗传的病有哪些 你造吗 这些特征容易隔代遗传