快速排序算法流程
终极管理员 知识笔记 99阅读
什么是快速排序算法？
答：这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。 快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。
快速排序算法时间复杂度是多少？
答：quick_sort (arr , p , par-1) // 将 [p , par-1] 作为待排序序列，重复进行分割 quick_sort (arr , par+1 , q) // 将 [par+1 , q] 作为待排序序列，重复进行分割 最坏情况下，快速排序算法的时间复杂度为 O (n 2) ，理想状态对应的时间复杂度为 O (nlogn) 。
快速排序是怎么回事？
答：到此，排序完全结束。 细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。 下面上个霸气的图来描述下整个算法的处理过程。
如何对快速排序进行说明分析？
答：前几回，在前面已经对 冒泡排序 、 直接插入排序 、 希尔排序 、 选择排序 做了说明分析。 这回，将对快速排序进行相关说明分析。 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。