排序算法----快速排序

快速排序和归并排序一样，也使用了分治思想。

最关键的步骤是分解，例如，对数组A[p..r]进行分解。划分为2个子数组A[p..q - 1]和A[q + 1..r]。A[p..q - 1]中每一个元素都小于等于A[q],A[q + 1..r]中的每一个元素都大于等于A[q]。

伪码：

 1 PARTITION(A,p,r)
 2 {
 3   x = A[r];
 4   i  = p - 1;
 5   for j = p to r -1
 6        if A[j] <= x
 7           i = i + 1
 8           exchange A[i] with A[j]
 9   exchange A[i + 1] with A[r]
10   return i + 1
11 }

View Code

分析：首先选择数组的最后一个元素作为主元，i 设为第一个元素下标减1。A[p..r -1]中的元素依次与主元进行比较，如果比主元小，就和A[i + 1]交换，i加 1（第一个比主元小的交换到数组的第一个位置，第二个比主元小的交换到数组的第二个位置... ...）。循环结束后，子数组A[p..i]的元素都小于等于主元，子数组A[i + 1..r - 1]的元素都大于主元。最后把主元和A[i + 1]进行交换。最后数组A[p..r]就分解为2个子数组，子数组A[p..i]元素都小于等于A[i + 1]，子数组A[i + 2..r]都大于A[i + 1]。

图例：

最后我们使用快速排序进行对数组的排序

伪码：

1 QUICKSORT(A,p,r)
2    if  p < r
3        q = PARTITION(A,p,r)
4        QUICKSORT(A,p,q - 1)
5        QUICKSORT(A,q + 1, r)

View Code

当p小于等于r时，数组中只有一个元素，显然是排序的。否则，分解为2个子数组，递归调用快速排序。

如果每次划分时，2个子数组分别包含了n - 1 和 0 个元素时，快速排序出现最坏情况，T(n) = O(n^2)。平均情况下T(n) = O(nlgn)

C++代码

 1 #define  EXCHANGE(a,b)    int temp = a;a = b;b = temp;
 2 
 3 int partition(int A[],int p,int r)
 4 {
 5     int x = A[r];
 6     int i = p - 1;
 7 
 8     for(int j = p; j < r;++j)
 9     {
10         if(A[j] < x)
11         {
12             ++i;
13             EXCHANGE(A[i],A[j])
14         }
15     }
16 
17     EXCHANGE(A[i + 1],A[r]);
18 
19     return i + 1;
20 }
21 
22 //快速排序，平均时间复杂度T(n) = O(nlgn)
23 void Quick_sort(int A[],int p,int r)
24 {
25     if(p < r)
26     {
27         int q = partition(A,p,r);
28         Quick_sort(A,p,q - 1);
29         Quick_sort(A,q + 1,r);
30     }
31 }

View Code