算法导论 第七章 快速排序
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 }转载于:https://www.cnblogs.com/lotushy/archive/2011/12/31/2309059.html
