快速排序总结

快速排序的优点是什么？

答：快速排序在排序算法中具有排序速度快，而且是就地排序等优点，使得在许多编程语言的内部元素排序实现中采用的就是快速排序，很多面试题中也经常遇到。

快速排序的基本思想是什么？

答：快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 将数组中所有元素都跟一个基准元素pivot比（随意选取，常取第一个或最后一个），比pivot小的划分成左边一块，比pivot大的划分成右边一块，得到两个子问题。

什么是快速排序算法？

答：这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。 快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的 空间复杂度 为 O (logn) ，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O (n) 。

如何对快速排序进行说明分析？

答：前几回，在前面已经对 冒泡排序 、 直接插入排序 、 希尔排序 、 选择排序 做了说明分析。 这回，将对快速排序进行相关说明分析。 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。