【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

时间:2023-03-08 16:27:34

在前面的博文(http://blog.****.net/jasonding1354/article/details/37736555)中介绍了作为分治策略的经典实例,即归并排序。并给出了递归形式和循环形式的c代码实例。可是归并排序有两个特点。一是在归并(即分治策略中的合并步骤)上花费的功夫较多,二是排序过程中须要使用额外的存储空间(异地排序算法<out
of place sort>)。

为了节省存储空间。出现了高速排序算法(原地排序in-place sort)。

高速排序是由东尼·霍尔所发展的一种排序算法。

在平均状况下,排序n个项目要O(nlogn)次比較。在最坏状况下则须要O(n2)次比較,但这样的状况并不常见。其实。高速排序通常明显比其它O(nlogn)算法更快,由于它的内部循环(inner loop)能够在大部分的架构上非常有效率地被实现出来。

此种排序的思路是:假设在分开的时候,不是从中间位置上分界,二是依照元素的大小分开为两个一大一小的子序列(一个子序列的全部元素大于还有一个子序列里的全部元素)。这种话。由于两个子序列之间的相对次序已经正确,全部在合并的时候就不须要花费不论什么时间。

尽管高速排序在归并上没有什么成本,可是因为分解是依照元素大小进行。因此在分解步骤破费工夫,即先付出代价;在合并的时候不用费力。即后享受劳动成果。

1、高速排序过程

(1)选择杠杆点(分界点、基准)。

在待排序的序列里面依照某种方式选取一个元素,即杠杆点。

(2)分解。以杠杆点为界,将序列分为两个子序列A[p..q-1]、A[q+1..r]。当中子序列A[p..q-1]里的全部元素小于等于杠杆点,还有一个子序列A[q+1,r]里的全部元素大于杠杆点。在这个分解退出之后。该基准就处于数列的中间位置。

(3)治之。递归对两个子序列进行高速排序,对子序列A[p..q-1]、A[q+1..r]排序。

(4)合并。将排好序的两个子序列合并为大序列。

由于两个子序列是原地排序的,将它们合并不须要操作。整个序列A[p..r]已排序。

【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

图1 高速排序流程举例

【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

图2 高速排序算法演示

2、伪代码及举例

高速排序算法最关键的是分解(Partition)过程,高速排序的时间成本取决于分解这一步。

PARTITION(A,m,n)
{
x = A[m];
i = m;
for(j=m+1;j<=n;j++)
{
if(A[j] <= x)
{
i = i+1;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i];
A[i] = A[m];
A[m] = temp;
return i;
}

高速排序的分解过程演演示样例如以下:

【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvSmFzb25EaW5nMTM1NA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" width="400" height="360" alt="">

图3 高速排序分解步骤演示

正如分解步骤的伪代码所描写叙述的,选择数组第一个元素“6”为杠杆点。在第(1)步中移动下标索引j。当找到小于杠杆点“6”的值时,移动下标索引i来交换数组元素(如第(2)步所看到的),依次类推。第(3)、(4)步,通过j不断寻找小于杠杆点的元素。并交换小于杠杆点的元素到数组的前半部分。

终于,在第(5)步。将杠杆点置于两个子数组之间。

当中。红色部分是杠杆点。黄色部分数组元素划分到第一部分,蓝色部分数组元素划分到第二部分。灰色部分数组元素师尚未划分的部分。

高速排序算法例如以下:

QUICKSORT(A,p,r)
{
if(p<r)
{
q = PARTITION(A,p,r);
QUICKSORT(A,p,q-1);
QUICKSORT(A,q+1,r);
}
}

3、高速排序C程序实例

#include <stdio.h>
#define CutOff 3
#define QUICK_ONLY typedef int ElemType; void Swap(ElemType *i, ElemType *j)
{
ElemType tmp;
tmp = *i;
*i = *j;
*j = tmp;
} void PrintElement(ElemType A[], int N, char *prompt)
{
printf("%s :\n",prompt);
for(int i=1;i <= N;i++){
printf("%5d",A[i-1]);
if(i % 10 == 0)
printf("\n");
}
printf("\n");
} ElemType Median3(ElemType A[], int Left, int Right)
{
int Center;
Center = (Left + Right)/2; if(A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if(A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if(A[Center] > A[Right])
Swap(&A[Center], &A[Right]); Swap(&A[Center], &A[Right-1]); return A[Right-1];
} void Reverse(ElemType A[], int Left, int Right)
{
if(A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
} void InsertionSort(ElemType A[], int N)
{
int i,j;
ElemType tmp;
for(i=1;i<N;i++){
tmp = A[i];
for(j=i;j>0 && A[j-1]>tmp;j--){
A[j] = A[j-1];
}
A[j] = tmp;
}
} void QSort(ElemType A[], int Left, int Right)
{
int i,j;
ElemType pivot; #ifdef QUICK_ONLY
if(Left+1 < Right){
#else
if(Left+CutOff <= Right){
#endif
i = Left;
j = Right - 1;
pivot = Median3(A, Left, Right);
for(;;){
while(A[++i] < pivot){}
while(A[--j] > pivot){}
if(i < j)
Swap(&A[i], &A[j]);
else
break;
}//for(;;) Swap(&A[i], &A[Right-1]);
QSort(A, Left, i-1);
QSort(A, i+1, Right);
}
#ifdef QUICK_ONLY
else
Reverse(A, Left, Right);
#else
else
InsertionSort(A+Left, Right-Left+1);
#endif
} void QuickSort(ElemType A[], int Size)
{
QSort(A, 0, Size-1);
} int main()
{
ElemType test_array[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
int num_size = sizeof(test_array)/sizeof(ElemType);
PrintElement(test_array,num_size,"The original array:");
QuickSort(test_array, num_size);
PrintElement(test_array,num_size,"The sorted array:");
return 0;
}

其执行结果为:

【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

图4 高速排序程序执行结果

说明:

(1)因为选择杠杆点对排序的花费时间有非常大的影响,假设输入时反序的话,这样选择第一个元素作为杠杆点(pivot),则全部元素被划为一边的子序列,这是非常差的结果。所以该程序使用的方法是三数中值切割法(函数Median3),即选取左端、右端和中心位置的三个元素的中值作为杠杆点。这样能有效降低高速排序大约5%的执行时间。

(2)小数组排序的问题。

对于非常小的数组,高速排序不如插入排序好,所以在QSort函数中,能够选择当Left+CutOff <= Right时,对小数组进行插入排序。

4、高速排序的时间复杂度分析

高速排序的时间复杂度体如今分解上,因此分解的成本将决定高速排序的成本。对于一个有n个元素的序列来说。分解的次数最多仅仅能是n-1。即每次分解都形成一个空子序列和一个包括n-1个元素的子序列;最少分解次数是logn,即每次分解出两个长度相当的子序列。

(1)最坏情况分析

高速排序的最坏情况划分行为发生在划分过程中产生的各自是包括n-1个元素的子序列和0个元素的子序列,故执行时间的递归表达式能够表示为:

T(n) = T(n-1)+T(0)+Θ(n) = T(n-1)+Θ(n),故其时间复杂度为T(n)=Θ(n2)。

(2)最好情况分析

最平衡的划分,得到两个子序列的大小相当,这样的情况下,其执行时间的递归式为:

T(n) ≤ 2T(n/2)+Θ(n)。该递归式的解为T(n) = O(nlgn)。

(3)平均情况分析

高速排序的平均情况执行时间与其最佳情况执行时间相近。

比如,如果划分过程总是产生9:1的划分,此时高速排序的执行时间递归式为:T(n) = T(9n/10)+T(n/10)+Θ(n)。这种结果是T(n)=Θ(nlogn)。

【从零学习经典算法系列】分治策略实例——高速排序(QuickSort)

图5 高速排序平均情况递归树

转载请注明作者及文章出处:http://blog.****.net/jasonding1354/article/details/38224967

參考资料:

《算法之道(第2版)》,邹恒明著,机械工业出版社

《算法导论(原书第2版)》,机械工业出版社

《数据结构与算法分析:C语言描写叙述》,机械工业出版社