精通八大排序算法系列一快速排序算法

精通八大排序算法系列：一、快速排序算法

作者 July 二零一一年一月四日

一、快速排序算法的基本特性

时间复杂度：O（n*lgn）

最坏：O（n^2）

空间复杂度：O（n*lgn）

不稳定。

快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n^2）。 通常是用于排序的最佳选择。因为，排序最快，也只能达到O（nlgn）。

二、快速排序算法的描述

算法导论，第7章

快速排序时基于分治模式处理的，

对一个典型子数组A[p...r]排序的分治过程为三个步骤：

1.分解：

A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得

A[p ..q-1] <= A[q] <= A[q+1 ..r]

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

3.合并。

三、快速排序算法

版本一：

QUICKSORT(A, p, r)

1 if p < r

2 then q ← PARTITION(A, p, r) //关键

3 QUICKSORT(A, p, q - 1)

4 QUICKSORT(A, q + 1, r)

数组划分

快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：

PARTITION(A, p, r)

1 x ← A[r]

2 i ← p - 1

3 for j ← p to r - 1

4 do if A[j] ≤ x

5 then i ← i + 1

6 exchange A[i] <-> A[j]

7 exchange A[i + 1] <-> A[r]

8 return i + 1

ok，咱们来举一个具体而完整的例子。

来对以下数组，进行快速排序，

2 8 7 1 3 5 6 4(主元)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库精通八大排序算法系列一快速排序算法在线全文阅读。