首页 > 编程之美 > 快速排序
2013
09-12

快速排序

快速排序是基于分治策略的一个排序算法,实现快速排序的分治过程如下:
分解:数组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]已排序。
实验代码如下:

该算法在最坏情况下的时间复杂性为T(n)=O(n^2),平均情况下的时间复杂性是O(nlogn)

最后编辑:
作者:Jianchihu
管理员——低调做事,低调做人

留下一个回复

你的email不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.