快速排序 标签

快速排序的分析与优化 有更新!

  |   0 评论   |   216 浏览

快速排序的介绍

快速排序是一种排序算法,对包含n个数的输入数组,最坏的情况运行时间为Θ(n^2)[Θ读作theta]。虽然这个最坏情况的运行时间比较差,但快速排序通常是用于排序的最佳的实用选择。这是因为其平均情况下的性能相当好:期望的运行时间为Θ(nlgn),且Θ(nlgn)记号中隐含的常数因子很小。另外,它还能够进行就地排序,在虚拟内存环境中也能很好的工作。

和归并排序一样,快速排序也是基于分治法(Divide and conquer):

  • 分解:数组A[p..r]被划分成两个(可能为空)的子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A[q],A[q+1..r]中的每个元素都大于等于A[q]。这样元素A[q]就位于其最终位置上了。
  • 解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序。
  • 合并:因为两个子数组是就地排序,不需要合并,整个数组已有序。