快速排序

来自"NOCOW"

目录 1 介绍 2 基本思想 3 操作 4 分析 5 代码

[编辑] 介绍

快排是基于分治思想的一种排序算法。快排的效率取决于选取为排序标准的键值能否尽可能将数据均分。

[编辑] 基本思想

分：选择一个基准键值A[i]，把所有元素按照大小分成两部分；（这样能确定一个元素的最后位置）

治：把两个子序列分别进行快排直到只剩下一个元素。

[编辑] 操作

[编辑] 分析

最坏情况下θ(n^2) 平均情况下为θ(nlgn)

[编辑] 代码

c

pascal