首页 > 代码库 > 【从零学习经典算法系列】分治策略实例——快速排序(QuickSort)
【从零学习经典算法系列】分治策略实例——快速排序(QuickSort)
在前面的博文(http://blog.csdn.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]已排序。
图1 快速排序流程举例
图2 快速排序算法演示
2、伪代码及举例
快速排序算法最关键的是分解(Partition)过程,快速排序的时间成本取决于分解这一步。
<span style="font-size:14px;">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; }</span>
快速排序的分解过程演示如下:
图3 快速排序分解步骤演示
正如分解步骤的伪代码所描述的,选择数组第一个元素“6”为杠杆点,在第(1)步中移动下标索引j,当找到小于杠杆点“6”的值时,移动下标索引i来交换数组元素(如第(2)步所示),依次类推,第(3)、(4)步,通过j不断寻找小于杠杆点的元素,并交换小于杠杆点的元素到数组的前半部分。最终,在第(5)步,将杠杆点置于两个子数组之间。
其中,红色部分是杠杆点,黄色部分数组元素划分到第一部分,蓝色部分数组元素划分到第二部分,灰色部分数组元素师尚未划分的部分。
<span style="font-size:14px;">QUICKSORT(A,p,r) { if(p<r) { q = PARTITION(A,p,r); QUICKSORT(A,p,q-1); QUICKSORT(A,q+1,r); } }</span>
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 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 < 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); } #ifndef QUICK_ONLY 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; }其运行结果为:
图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)。
图5 快速排序平均情况递归树
转载请注明作者及文章出处:http://blog.csdn.net/jasonding1354/article/details/38224967
参考资料:
《算法之道(第2版)》,邹恒明著,机械工业出版社
《算法导论(原书第2版)》,机械工业出版社
《数据结构与算法分析:C语言描述》,机械工业出版社