|
快速排序 快速排序（Quick Sort）通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序 快速排序三个步骤 分解（Divide）将原问题分解为若干个子问题此步骤亦称为划分 求解（Conquer）递归地解各子问题若子问题的规模足够小则直接求解 组合（Combine）将各子问题的解组合成原问题的解 一趟快速排序采用从两头向中间夹入比较同时交换与基准键值逆序的结点 快速排序算法 快速排序的最坏时间复杂度为O(n)最好时间复杂度为O(nlgn)平均时间复杂度为O(nlgn) 快速排序方法是不稳定的 |
