【21天学习挑战赛—经典算法】快速排序

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

CSDN—21天学习挑战赛—【经典算法】

学习专栏地址

经典算法_一头小山猪的博客-CSDN博客

文章

一文学懂经典算法系列之：快速排序)

---

快速排序 QuickSort

快速排序是对冒泡排序的一种改进，也是一种 交互相邻元素的算法，快速排序所采用的思想是分治的思想。所谓分治，就是指以一个数为基准，将序列中的其他数往它两边“扔”。以从小到大排序为例，比它小的都“扔”到它的左边，比它大的都“扔”到它的右边，然后左右两边再分别重复这个操作，不停地分，直至分到每一个分区的基准数的左边或者右边都只剩一个数为止。

基本思路

• 在待排序的数列中，首先要找一个数字作为基准数
• 一般选择第 1 个数字作为基准数，
• 然后把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，
• 把大于基准数的元素移动到待排序的数列的右边。
• 此时左右两个分区的元素就是 基准数右边的所有数都大于基准数左边的数；
• 之后使用同样的思路 从左右两个分区的元素分别按照上面思路，对每个分区找出基准数，然后移动左右数据，
• 最后分区只剩下一个数时，及完成了排序

示意图

时间复杂度

最坏情况下的时间复杂度和冒泡排序一样，是 O(n2)，这种情况并不常见。
一般情况下快速排序的平均时间复杂度是 O(nlogn)，

• 快速排序被认为是相同数量级的所有排序算法中，平均性能最好的。

快速排序算法，C语言快速排序算法详解
快速排序-菜鸟教程