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

冒泡排序

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

基本思想

快速排序(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)

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180823G07TBI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券