快速排序

算法导论第七章快速排序

C程序代码如下：

 1 /**
 2  * Quicksort
 3  * 分解： 将数组A[p...r]划分成两个子数组A[p...q - 1]和A[q+1...r]，使得A[p...q-1]
 4  * 中的元素均小于或等于A[q]；A[q+1...r]中的元素均大于A[q]。
 5  * 特点： 1. 就地排序 2.平均时间复杂度为nlgn，最坏为n的2次方。
 6  */
 7 #include <stdio.h>
 8 #define ARRAY_LENGTH(a) (sizeof(a)/sizeof(*a))
 9 
10 inline void exchange(int* a, int* b) {
11         int tmp = *a;
12         *a = *b;
13         *b = tmp;
14 }
15 
16 int privatekey(int * A, int p, int r) {
17         int tmp = 0;
18         int x = A[r];
19         int i = p - 1;
20         int j = p;
21         for(; j < r; j++) {
22                 if (A[j] <= x) {
23                         i++;
24 
25                         exchange(A + i, A + j);
26                 }
27         }
28 
29         exchange(A + i + 1, A + r);
30 
31         return i + 1;
32 }
33 
34 void quicksort(int * A, int p, int r) {
35         if (p < r) {
36                 int q = privatekey(A,p,r);
37                 quicksort(A,p,q-1);
38                 quicksort(A,q+1,r);
39         }
40 }
41 
42 int main() {
43         int A[] = {2,8,7,1,3,5,6,4};
44         int len = sizeof(A) / sizeof(int);
45         int i = 0;
46         quicksort(A,0,len - 1);
47         for(i = 0; i < len; i++)
48                 printf("%d,", A[i]);
49         printf("\n");
50         return 0;
51 }

尾递归的实现如下：

1 void quicksort_tail(int * A, int p, int r) {
2         while (p < r) {
3                 int q = privatekey(A,p,r);
4                 quicksort_tail(A,p,q-1);
5                 p = q + 1;
6         }
7 }