快速排序及其分析2011-07-27 14:35 by zabery, 77 visits, 收藏, 编辑前言快速排序的平均情况下是O(nlogn),但是一般都比其他运行时间为O(nlogn)的算法都要快,因为它隐藏的常数因子比较小,但是在最坏情况之下,快速排序的运行时间是O(n2)。 快速排序过程快速排序采用的思想是分治思想,就像合并排序算法的思想一样,合并排序算法是从数组的中间开始分治,直到分为N个分组,最后分别合并N个分组的解。如下图,有原始数组A = {1, 3, 4, 5, 7, 2, 6, 8, 0} 快 速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都 不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确 位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。 基准基准的挑选会影响到算法的性能,一般情况将序列的第一个元素作为基准。 分区算法设 两个指针left和right,一个从左往右扫描,一个从右往左扫描;对于左指针,如果左指针所指的元素的值小于或者等于基准值,那么指针往右移一位,如 果大于基准值,则和基准值交换;同理,对于右指针,如果右指针所指的元素的值大于或者等于基准值,那么指针往左移一位,如果小于基准值,则和基准值交换。 代码如下: 1: int Partition(int A[], int p, int r) 2: {
3: int privot = A[p]; //基准 4: // 设两个指针 5: int left = p; //从左往右扫描 6: int right = r; //从右往左扫描 7:
8: while (right > left) 9: {
10: while (right > left && A[right] >= privot) 11: {
12: right--;
13: }
14:
15: A[left] = A[right];
16:
17: while (right > left && A[left] <= privot) 18: {
19: left++;
20: }
21:
22: A[right] = A[left];
23: }
24:
25: A[left] = privot;
26: return left; 27: }
1: void QuickSort(int A[], int p, int r) 2: {
3: int pivot; 4:
5: if (r > p) 6: {
7: pivot = Partition(A, p, r);
8: QuickSort(A, p, pivot-1);
9: QuickSort(A, pivot+1, r);
10: }
11: }
性能分析最好情况每次基准的最终位置都是在数组中间位置,从而使规模为N的问题分为2个规模为N/2的问题,即T(n) = 2T(n/2) + Θ(n),用递归树分析或者主定理得到时间T(n) = O(nlogn)。 最坏情况每次基准的最终位置都是第一个位置,从而规模为N的问题分为一个规模为N-1的问题,即T(n) = T(n-1) + Θ(n),用递归树分析可得运行时间T(n) = O(n2)。 平均情况假设规模为N的问题分为一个规模为9/10N的问题和规模为1/10N的问题,即T(n) = T(9n/10) + T(n/10) + Θ(n),用递归树分析可得T(n) = O(nlogn),而且比分区9:1要更平均(也就是情况更好)的概率为80%,所以在绝大部分情况下快速排序算法的运行时间为O(nlogn)。 |
|