快速排序算法讲解

电玩女神 2022-05-15 08:39 186阅读 0赞

看到名字，感觉很腻害，嗯，今天我们来讲解下这个比较腻害的算法

思路如下：

首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

比如我们有一个数组\{10,1,18,30,23,12,7,5,18,17\}，我们现在要使用快速排序算法对其进行排序

要比较，总先要找一个值才行撒，我们也不挑剔，我们要先找一个基准值，比如第一个值，10

接下来，我们要干啥呢，我们要做一件事，让基准值到达一个位置，什么位置呢

【数组1】基准值【数组2】，要求数组1都要小于等于基准值，数组2都要大于等于基准值

比如一遍之后的结果是【5, 1, 7】10【23, 12, 30, 18, 18, 17】，然后再分别在把左【5, 1, 7】右【23, 12, 30, 18, 18, 17】两个数组以同样的方式进行排序，最终整体排序ok

我们在数组的第一个位置放个标识m，最后一个位置放一个标识n，m一直向后移，直到遇到一个比m大的，n一直向左移，直到遇到一个比n小的，然后交换，交换完之后继续循环。

如上，我们先选择右边先行，右向左  17-》18-》5，我们发现一个比10小的了，此时左边的下标仍然是0，所以用5替换掉下标为m，即下标为0对应的值，即第一个10，得到：\[5, 1, 18, 30, 23, 12, 7, 5, 18, 17\]，此时m为7，n为0

左向右 5-》1-》18，我们发现一个比10大的了，做法和上面的一样，用18替换,下标为m,即下标为7对应的值，即右边的5，得到

\[5, 1, 18, 30, 23, 12, 7, 18, 18, 17\]，此时m为7，n是2

嗯，我们发现左下标还是小于右下标，所以可以继续从右向左和从左向右寻找

右往左，18-》7，发现下标为6的（数字为7）小于基准值10，此时n是2，所以替换掉下标为2的值，得到\[5, 1, 7, 30, 23, 12, 7, 18, 18, 17\]

左往右，7-》30，发现下标为3（数字为30）大于基准值10，此时n是6，所以替换掉下标为6的值，得到\[5, 1, 7, 30, 23, 12, 30, 18, 18, 17\]

然后继续循环，没发现右边有比10大的，左边有比10小的，则此轮循环结束，这个时候需要把m位置替换成基准值，得到\[5, 1, 7, 10, 23, 12, 30, 18, 18, 17\]

这个时候把左边\[5, 1, 7和右边23, 12, 30, 18, 18, 17\]分别使用上面的方法分别进行循环（这个地方使用了递归）

最后得到总循环结果\[1, 5, 7, 10, 12, 17, 18, 18, 23, 30\]

最优情况如下

快速排序需要栈空间来实现递归，如果数组按局等方式被分割时，则最大的递归深度为 log n，需要的栈空间为 O(log n)。

比较坏的情况下在递归的每一级上，数组分割成长度为0的左子数组和长度为 n - 1 的右数组。这种情况下，递归的深度就成为 n，需要的栈空间为 O(n)。

最坏情况如下

当基数值不能很好地分割数组，即基准值将数组分成一个子数组中有一个记录，而另一个子组组有 n -1 个记录时，下一次的子数组只比原来数组小 1，这是快速排序的最差的情况。如果这种情况发生在每次划分过程中，那么快速排序就退化成了冒泡排序，其时间复杂度为O(n2)。

稳定性如下

因为快速排序在进行交换时，只是根据比较基数值判断是否交换，且不是相邻元素来交换，在交换过程中可能改变相同元素的顺序，因此是一种不稳定的排序算法。

点击下方链接获取具体实现代码

[java实现快排][java]

[python实现快排][python]

[go实现快排][go]

[java]: https://blog.csdn.net/stronglyh/article/details/82177450
[python]: https://blog.csdn.net/stronglyh/article/details/82155877
[go]: https://blog.csdn.net/stronglyh/article/details/82215232

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关【排序算法】- 快速排序

文章目录 1 快速排序法介绍: 2 快速排序法示意图: 3 快速排序法应用实例: 1 快速排序法介绍: 快速排序（Quicksort）是对`冒泡

桃扇骨/ 2022年12月20日 06:04/ 0 赞/ 231 阅读

相关排序算法——快速排序

排序算法——快速排序 > 快速排序通过一趟排序将待排序序列分隔成独立的两部分，其中一部分序列的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个

你的名字/ 2022年11月20日 08:04/ 0 赞/ 265 阅读

相关快速排序(详细讲解)

如今的面试里面,快速排序成了一项必须要掌握的技能,面试官考快排的概率非常大,不管是从思路上还是实践上,都基本必问.快速排序是一个既高效又不浪费空间的一种排序算法.下面来详细讲解

朴灿烈づ我的快乐病毒、/ 2022年09月06日 10:22/ 0 赞/ 180 阅读

相关算法——排序——快速排序

快速排序： 1.原地排序 2.O(nlogn)（最坏O(n^2) 这也是严重缺点之一） 3.要尽量保证输入的元素是基本无序的，因为在有序情况下，其时间复杂度是O(n^2)

朴灿烈づ我的快乐病毒、/ 2022年07月27日 11:50/ 0 赞/ 229 阅读

相关排序算法——快速排序

前言快速排序采用了分治法，即将原问题划分成为若干个规模更小且与原问题相似的子问题，然后递归地解决这些子问题，最后将他们组合起来。快速排序的思想是：假设数据元素存放在

淡淡的烟草味﹌/ 2022年06月12日 00:20/ 0 赞/ 338 阅读

相关快速排序讲解+示意图

include <stdio.h> void quickSort(int ,int,int); int findPos(int ,int,in

一时失言乱红尘/ 2022年06月05日 22:12/ 0 赞/ 196 阅读

相关快速排序算法详细讲解c++版

快速排序算法 1.首先我需要对快速排序算法下个定义：什么是快排呢？或者是排序的指导思想比如一个待排序的数组 int iArray\[\] = \{5,4,45,8

布满荆棘的人生/ 2022年06月03日 01:49/ 0 赞/ 201 阅读

相关快速排序算法讲解

看到名字，感觉很腻害，嗯，今天我们来讲解下这个比较腻害的算法思路如下：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有

电玩女神/ 2022年05月15日 08:39/ 0 赞/ 187 阅读

相关排序算法：快速排序

一、前言快速排序是一种交换排序，它由C. A. R. Hoare在1962年提出。 -------------------- 二、算法思想快

我不是女神ヾ/ 2022年04月05日 14:00/ 0 赞/ 385 阅读

相关排序算法---快速排序

基本思路：快速排序，数组冲两边出发。首先取一个关键字。在第一次排序后。大于和小于关键字的各在关键字两边。然后在对两边重复上面步骤，取关键字，排序。直

电玩女神/ 2022年03月11日 04:47/ 0 赞/ 337 阅读