首页 / 软件开发 / 数据结构与算法 / 【算法导论】排序 （三）：快速排序 深入分析

【算法导论】排序 （三）：快速排序 深入分析2014-01-01 csdn shuangde800五、快速排序

快速排序是最常用的一种排序算法，包括C的qsort，C++和Java的sort，都采用了快 排（C++和Java的sort经过了优化，还混合了其他排序算法）。

快排最坏情况O（ n^2 ），但平均效率 O（n lg n），而且这个O（n lg n）几号中隐含的常数因子很小，快排可以说是最快的排序算法，并非浪得虚名 。另外它还是就地排序。

快速排序是基于分治模式的：

分解：数组A【p..r】被划分成两个（可能空）子数组A【p..q-1】和A【q+1..r】，使得A【p..q-1】中的 每个元素都小于等于A（q），而且，小于等于A【q+1..r】中的元素。下 标q 也在返个划分过程中迕行计算。

解决：通过递归调用快速排序，对子数组A【p..q-1】和A【q+1..r】排序。

合并：因为两个 子数组使就地排序的，将它们的合并不需要操作：整个数组A【p..r】已排序。

下面过程实现快速排 序：

数组划分：Partition（关键，它对子数组A【p..r】进行就地重排）