冒泡排序
基本思想|演示|算法代码|性能
基本思想
快速排序(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)
领取专属 10元无门槛券
私享最新 技术干货