数据结构中的快速排序
墨初 知识笔记 74阅读
什么是快速排序？
答：快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。
快速排序和递归排序有什么区别？
答：第一趟 排序 ： 快速排序 是找出一个元素（理论上可以随便找一个）作为基准 (pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到 排序 后的正确位置。 递归 排序 ：第二步就是对高段位和地段为两部分进行递归 排序 。
快速排序的空间复杂度是多少？
答：快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。 所以我们一般认为快速排序的空间复杂度为 O (logn) 。
快速排序时间复杂度和冒泡排序一样吗？
答：但是快速排序在最坏情况下的 时间复杂度 和冒泡排序一样，是 O (n 2) ，实际上每次比较都需要交换，但是这种情况并不常见。 我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 O (nlogn) ，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。