​
​

前言：
✌ 作者简介：游坦之 ✌
🏆 大学软件工程在读，希望学到真本领，经世致用 🏆
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
💬 人生格言：丑且益坚，病当益壮💬
🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

快速排序

@TOC

什么是快速排序？

快速排序是对冒泡排序的一种改进。

快速排序的具体步骤

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

示例

对{29,10,14,37,14}进行排序

第一步，i=0,j=4，ref=29，两个位置的元素相互比较，a[0]>a[4],a[0]的位置置换成a[4]，i++;此时的序列变为{14,10,14,37,14};

第二步，对比此时两个位置的元素，10<14，i往后移动一位，i变为2，j为4.

第三步，对比此时两个元素的位置14==14，i往后移动一位，i变为3，j为4，此时37>14，置换两个元素的位置，此时的序列变为

{14,10,14,14,37}，j--，i==j,将此时的位置置换为ref，最后的序列为{14,10,14,29,37}。此时的序列，29前面的都小于他，29后面的都大于他。

重复以上过程，就可以得到一个从小到大有序的序列。

时间复杂度

平均需要排序logn趟，所以平均时间复杂度是O(n*logn)。

稳定性：由于排序的过程中，可能使相同元素的前后顺序发生变化，所以快速排序是一个不稳定的算法。

✨$\textcolor{blue}{原创不易，为了最基础的欲望！}$ <br/>
👍 $\textcolor{green}{点赞，不会损失一匹布！}$ <br/>
⭐️ $\textcolor{green}{收藏，不会丢失一厘金！}$ <br/>
✏️ $\textcolor{green}{留下痕迹，却会温暖作者的心！}$ <br/>