人人网魔力学堂:9.9.1 快速排序算法(1)
来源:百度文库 编辑:中财网 时间:2024/04/29 17:50:10
9.9.1 快速排序算法(1)
快速排序(Quick Sort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
从字面上感觉不出它的好处来。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序。我们通过代码的讲解来学习快速排序的精妙。
我们来看代码。
- /* 对顺序表L作快速排序 */
- void QuickSort(SqList *L)
- {
- QSort(L,1,L->length);
- }
又是一句代码,和归并排序一样,由于需要递归调用,因此我们外封装了一个函数。现在我们来看QSort的实现。
- /* 对顺序表L中的子序列L->r[low..high]作快速排序 */
- void QSort(SqList *L,int low,int high)
- {
- int pivot;
- if(low
{ - pivot=Partition(L,low,high); /*将L->r[low..high]一分为二,*/
- /*算出枢轴值pivot */
- QSort(L,low,pivot-1); /*对低子表递归排序 */
- QSort(L,pivot+1,high); /*对高子表递归排序 */
- }
- }
从这里,你应该能理解前面代码“QSort(L,1,L‐>length);”中1和L‐>length代码的意思了,它就是当前待排序大下标值high。
的序列最小下标值low和最这一段代码的核心是“pivot=Partition(L,low,high);”在执行它之前,L.r的数组值为{50,10,90,30,70,40,80,60,20}。Partition函数要做的,就是先选取当中的一个关键字,比如选择第一个关键字50,然后想尽办法将它放到一个位置,使得它左边的值都比它小,右边的值比它大,我们将这样的关键字称为枢轴(piv)。
在经过Partition(L,1,9)的执行之后,数组变成{20,10,40,30,50,70,80,60,90},并返回值5给pivot,数字5表明50放置在数组下标为5的位置。此时,计算机把原来的数组变成了两个位于50左和右小数组{20,10,40,30}和{70,80,60,90},而后的递归调用“QSort(L,1,5‐1);”和“QSort(L,5+1,9);”语句,其实就是在对{20,10,40,30}和{70,80,60,90}分别进行同样的Partition操作,直到顺序全部正确为止。
到了这里,应该说理解起来还不算困难。下面我们就来看看快速排序最关键的Partition函数实现。
- /* 交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置 */
- /* 此时在它之前(后)的记录均不大(小)于它。 */
- 1 int Partition(SqList *L,int low,int high)
- 2 {
- 3 int pivotkey;
- 4 pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
- 5 while(low
6 { - 7 while(low
r[high]>=pivotkey) - 8 high--;
- 9 swap(L,low,high); /* 将比枢轴记录小的记录交换到低端 */
- 10 while(low
r[low]<=pivotkey) - 11 low++;
- 12 swap(L,low,high); /* 将比枢轴记录大的记录交换到高端 */
- 13 }
- 14 return low; /* 返回枢轴所在位置 */
- 15 }
1.程序开始执行,此时low=1,high=L.length=9。第4行,我们将L.r[low]=L.r[1]=50赋值给枢轴变量pivotkey,如图9‐9‐1所示。
2.第5~13行为while循环,目前low=1 3.第7行,L.r[high]=L.r[9]=20≯pivotkey=50,因此不执行第8行。 4.第9行,交换L.r[low]与L.r[high]的值,使得L.r[1]=20,L.r[9]=50。为什么要交换,就是因为通过第7行的比较知道,L.r[high]是一个比pivotkey=50(即L.r[low])还要小的值,因此它应该交换到50的左侧,如图9‐9‐2所示。 5.第10行,当L.r[low]= L.r[1]=20,pivotkey=50,L.r[low] 6.第12行,交换L.r[low]=L.r[3]与L.r[high]=L.r[9]的值,使得L.r[3]=50,L.r[9]=90。此时相当于将一个比50大的值90交换到了50的右边。注意此时low已经指向了3,如图9‐9‐3所示。