快速排序算法讲解

电玩女神 2022-05-15 08:39 201阅读 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 条评论，201人围观）

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

相关阅读

相关快速排序_详解快速排序算法

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对[冒泡排序][Link 1]算法的一种改进。快速排序的排序流程快速排序算法通

快来打我*/ 2023年09月28日 22:53/ 0 赞/ 130 阅读

相关 java快速排序讲解

今天最后一篇排序了快速排序，快速排序，就是快速的排列一个数组是什么代码敢让它称之为快速排序让我们看看其中的原理： --------------------

淩亂°似流年/ 2023年03月01日 13:54/ 0 赞/ 6 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关快速排序算法讲解

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

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

相关排序算法：快速排序

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

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

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

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

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