void quicksort( int A[], int p, int r) { int i; if(p < r) { i = partition(A, p, r); quicksort(A, 0, i - 1); quicksort(A, i + 1, r); } }
其中partition函数将得到X所在的位置i（在这里总以数组的最后一个元素为轴）。 int partition( int A[], int p, int r) { int i = p - 1, j; for(j = p; j < r; j++) { if(A[j] >= A[r]) { i++; swap(&A[i], &A[j]); } } swap(&A[i + 1], &A[r]); return i + 1; }
由于总是选择数组的最后一个元素做为轴，因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素，或元素很少的情况，即X最大或比较大。这样使quicksort将出现最坏的情况，也就是时间复杂度为 O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的（时间复杂度为 O(nlogn)），也就是说，最坏情况很难出现。 int new_random( int min, int max) { return (min + ( int)((( float)rand()/RAND_MAX)*(max - min))); } int randomize_partition( int A[], int p, int r) { int i = new_random(p, r); swap(&A[i], &A[r]); return partition(A, p, r); }
完整的代码如下 #include <stdio.h> #include <stdlib.h> void out_int_array( int data[], int n) { int i; for(i = 0; i < n; i++) { printf( " %d ", data[i]); } printf( " \n "); } void swap( int *a, int *b) { int x; x = *a; *a = *b; *b = x; } int new_random( int min, int max) { return (min + ( int)((( float)rand()/RAND_MAX)*(max - min))); } int partition( int A[], int p, int r) { int i = p - 1, j; for(j = p; j < r; j++) { if(A[j] >= A[r]) { i++; swap(&A[i], &A[j]); } } swap(&A[i + 1], &A[r]); return i + 1; } void quicksort( int A[], int p, int r) { int i; if(p < r) { i = partition(A, p, r); quicksort(A, 0, i - 1); quicksort(A, i + 1, r); } } int randomize_partition( int A[], int p, int r) { int i = new_random(p, r); swap(&A[i], &A[r]); return partition(A, p, r); } void randomize_quicksort( int A[], int p, int r) { int i; if(p < r) { i = randomize_partition(A, p, r); quicksort(A, 0, i - 1); quicksort(A, i + 1, r); } } int main() { int A[] = { 4, 1, 44, - 12, 5, 125, 30}; int B[] = { 4, 1, 44, - 12, 5, 125, 30}; out_int_array(A, 7); quicksort(A, 0, 6); out_int_array(A, 7); printf( " --------------------------randomize-----------------------------\n "); srand((unsigned)time( NULL )); randomize_quicksort(B, 0, 6); out_int_array(B, 7); return 0; }