经典排序算法——快速排序

经典排序算法——快速排序

1 快速排序的思想

快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另—部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

2 快速排序的实现

/* 交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L,int low,int high)
{
int pivotkey;

pivotkey=L->r[low]; /* 用子表的第一个记录作枢轴记录 */
while(low<high) /* 从表的两端交替地向中间扫描 */
{
while(low<high&&L->r[high]>=pivotkey)
high--;
swap(L,low,high);/* 将比枢轴记录小的记录交换到低端 */
while(low<high&&L->r[low]<=pivotkey)
low++;
swap(L,low,high);/* 将比枢轴记录大的记录交换到高端 */
}
return low; /* 返回枢轴所在位置 */
}

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); /* 将L->r[low..high]一分为二,算出枢轴值pivot */
QSort(L,low,pivot-1); /* 对低子表递归排序 */
QSort(L,pivot+1,high); /* 对高子表递归排序 */
}
}

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}

​Partiotion()​​函数要做的,就是先选取一个当中的一个关键字,想尽办法将它放到一个位置,使得左边的值都比它小,右边的值比它大,称这样的关键字称为枢轴(pivot)。

3 快速排序的执行流程

假设我们要排序的序列为​​{50,10,90,30,70,40,80,60,20}​​,执行流程如下:

  1. 程序开始执行,此时low=1,high=L->length=9。第4行,我们将​​L.row[low]=L.r[1]=50​​​赋值给枢轴变量​​pivotkey​​,如图所示。

经典排序算法——快速排序

  1. 第5-13行为while循环,目前low=1<high=9,执行内部语句。
  2. 第7行,​​L.r[high]=L.r[9]=20​​​不大于​​pivitkey=50​​,因此不执行第8行。
  3. 第9行,交换​​L.r[low]​​​与​​L.r[high]​​​的值,使得​​L.r[1]=20​​​,​​L.r[9]=50​​,如图所示。

经典排序算法——快速排序

  1. 第10行,当L.r[low]=L.r[1]=20, pivotkey=50,L.r[low]<pivotkey,因此第11行,low++,此时low=2。继续循环,L.r[2]=10<50,low++,此时low=3。L.r[3]=90>50,退出循环。
  2. 第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,如下图所示。

经典排序算法——快速排序

  1. 继续第5行,因为low=3<high=9,执行循环体。
  2. 第7行吗,当L.r[high]=L.r[9]=90, pivotkey=50,L.r[high]>pivotkey,因此第8行,high-,此时high=8。继续循环,L.r[8]=60>50, high-,此时high=7。L.r[7]=80>50,high-,此时high=6。L.r[6]=40<50,退出循环。
  3. 第9行,交换L.r[low]=L.r[3]=50与L.r[high]=L.r[6]=40的值,使得L.r[3]=40,L.r[6]=50,如下图所示。

经典排序算法——快速排序

  1. 第10行,当L.r[low]=L.r[3]=40, pivotkey=50, L.r[low]<pivotkey,因此第11行, low++,此时low=4。继续循环L.r[4]=30<50,low++,此时low=5。L.r[5]=70>50,退出循环。
  2. 12行,交换L.r[low]=L.r[5]=70与L.r[high]=L.r[6]=50的值,使得L.r[5]=50,L.r[6]=70,如图所示。

经典排序算法——快速排序

  1. 再次循环。因low=5<high=6,执行循环体后, low=hlgh=5,退出循环,如下图所示。

经典排序算法——快速排序

  1. 最后第14行,返回low的值5。函数执行完成。接下来就是递归调用​​QSort(L,1,5-1)​​​和​​QSort(L,5+1,9)​​​,分别进行同样的​​Partiotion​​操作,直到顺序全部正确为止。
发表评论

相关文章