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

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

作者 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(主元)

一、

i p/j

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

j指的2<=4，于是i++，i也指到2，2和2互换，原数组不变。

j后移，直到指向1..

二、

j（指向1）<=4，于是i++

i指向了8，所以8与1交换。

数组变成了：

i j

2 1 7 8 3 5 6 4

三、j后移，指向了3,3<=4，于是i++

i这是指向了7，于是7与3交换。

数组变成了：

i j

2 1 3 8 7 5 6 4

四、j继续后移，发现没有再比4小的数，所以，执行到了最后一步，

即上述PARTITION(A, p, r)代码部分的 第7行。

因此，i后移一个单位，指向了8

i j

2 1 3 8 7 5 6 4

A[i + 1] <-> A[r]，即8与4交换，所以，数组最终变成了如下形式，

2 1 3 4 7 5 6 8

ok，快速排序第一趟完成。

4把整个数组分成了俩部分，2 1 3,7 5 6 8，再递归对这俩部分分别快速排序。

i p/j

2 1 3(主元)

2与2互换，不变，然后又是1与1互换，还是不变，最后，3与3互换，不变，最终，3把2 1 3，分成了俩部分，2 1，和3.

再对2 1，递归排序，最终结果成为了1 2 3.

7 5 6 8(主元)，7、5、6、都比8小，所以第一趟，还是7 5 6 8，

不过，此刻8把7 5 6 8，分成了 7 5 6，和8.[7 5 6->5 7 6->5 6 7]

再对7 5 6，递归排序，最终结果变成5 6 7 8。

ok，所有过程，全部分析完成。

最后，看下我画的图：

快速排序算法版本二

不过，这个版本不再选取（如上第一版本的）数组的最后一个元素为主元，

而是选择，数组中的第一个元素为主元。

/**************************************************/

/* 函数功能：快速排序算法 */

/* 函数参数：结构类型table的指针变量tab */

/* 整型变量left和right左右边界的下标 */

/* 函数返回值：空 */

/* 文件名：quicsort.c 函数名：quicksort () */

/**************************************************/

void quicksort(table *tab,intleft,int right)

{

inti,j;

if(left<right)

{

i=left;j=right;

tab->r[0]=tab->r[i]; //准备以本次最左边的元素值为标准进行划分，先保存其值

do

{

while(tab->r[j].key>tab->r[0].key&&i<j)

j--; //从右向左找第1个小于标准值的位置j

if(i<j) //找到了，位置为j

{

tab->r[i].key=tab->r[j].key;i++;

} //将第j个元素置于左端并重置i

while(tab->r[i].key<tab->r[0].key&&i<j)

i++; //从左向右找第1个大于标准值的位置i

if(i<j) //找到了，位置为i

{

tab->r[j].key=tab->r[i].key;j--;

} //将第i个元素置于右端并重置j

}while(i!=j);

tab->r[i]=tab->r[0]; //将标准值放入它的最终位置,本次划分结束

quicksort(tab,left,i-1); //对标准值左半部递归调用本函数

quicksort(tab,i+1,right); //对标准值右半部递归调用本函数

}

}

----------------

ok，咱们，还是以上述相同的数组，应用此快排算法的版本二，来演示此排序过程：

这次，以数组中的第一个元素2为主元。

2(主) 8 7 1 3 5 6 4

请细看：

2 8 7 1 3 5 6 4

i-> <-j

(找大) (找小)

一、j

j找第一个小于2的元素1,1赋给(覆盖重置)i所指元素2

得到：

1 8 7 3 5 6 4

i j

二、i

i找到第一个大于2的元素8,8赋给(覆盖重置)j所指元素(NULL<-8)

1 7 8 3 5 6 4

i <-j

三、j

j继续左移，在与i碰头之前，没有找到比2小的元素，结束。

最后，主元2补上。

第一趟快排结束之后，数组变成：

1 2 7 8 3 5 6 4

第二趟，

7 8 3 5 6 4

i-> <-j

(找大) (找小)

一、j

j找到4，比主元7小，4赋给7所处位置

得到：

4 8 3 5 6

i-> j

二、i

i找比7大的第一个元素8,8覆盖j所指元素(NULL)

4 3 5 6 8

i j

4 6 3 5 8

i-> j

i与j碰头，结束。

第三趟：

4 6 3 5 7 8

......

以下，分析原理，一致，略过。

最后的结果，如下图所示：

1 2 3 4 5 6 7 8

相信，经过以上内容的具体分析，你一定明了了。

最后，贴一下我画的关于这个排序过程的图：

完。一月五日补充。

OK,上述俩种算法，明白一种即可。

-------------------------------------------------------------

五、快速排序的最坏情况和最快情况。

最坏情况发生在划分过程产生的俩个区域分别包含n-1个元素和一个0元素的时候，

即假设算法每一次递归调用过程中都出现了，这种划分不对称。那么划分的代价为O（n）， 因为对一个大小 …… 此处隐藏：2675字，全部文档内容请下载后查看。喜欢就下载吧 ……