经典排序算法——快速排序

冒泡排序

基本思想|演示|算法代码|性能

基本思想

快速排序（Quick Sort）是冒泡排序算法的一种改进，它通过设立枢轴元素（首元素），经过一趟排序操作将代排数据分割为独立的两部分，其中一部分的数据都要比该枢轴元素小，另一部分则都比该枢轴元素大。接着对分割开的两部分元素进行上述操作，整个排序过程按照递归思想进行，直到整组数据有序为止。

以数据4、8、3、7、5、1、2、6为例，以下仅展示一趟快速排序操作。

复制首元素作为枢轴元素，使其所在位置元素可被改写而不丢失数据

首先从后向前比较，将比枢轴元素4小的元素赋给low指向的位置元素；6>4，high指向前一个元素，接着进行比较

2

将比枢轴元素大的数据赋给low指向的位置元素后，从前向后比较，将比枢轴元素大的数据赋给右侧high指向的位置元素

8>4，将8赋给high指向的位置元素

然后从后向前比较，重复以上操作

从前向后比较

3

从后向前比较

5>4，high指向前一个元素，与low重合，此时循环终止

将枢轴元素赋给low指向的位置元素

按照递归思想，分别对左右两侧元素进行上述排序操作

重复这种排序操作，直到整组数据有序，排序终止

第二趟排序后的序列为1 2 3 4 5 7 8 6

第三趟排序后的序列为1 2 3 4 5 6 7 8

快速排序算法分为两个部分，分别为快速划分算法和递归排序算法

C++代码

Python代码

Java代码

快速排序算法是一种不稳定的排序算法，平均时间复杂度为O(nlogn)，平均空间复杂度为O(logn)