复习快速排序,用C语言实现:
#include <stdio.h> int quicksort(int begin, int end, int a[], int len); void main() { int a[] = {33, 22, 6, 5, 7, 3, 8, 9}; int len = sizeof(a)/sizeof(int); int i=0; int j=len-1; int pivot; pivot = quicksort(i, j, a, len); //printf(" pivot:%d ", pivot); //for(i=0; i<len; i++) //{ // printf("%d ", a[i]); //} } int quicksort(int begin, int end, int a[], int len) { int tmp = 0; for(tmp=begin; tmp<=end; tmp++) { printf("%d ", a[tmp]); } printf(" "); int i=begin; int j = end; int key = a[i]; //simple quick sort while(i<j) { while(a[j]>key && j>=0 && i<j) { j--; } if(j>=0 && i<j) { a[i] = a[j]; } while(a[i]<key && i<len && i<j) { i++; } if(i<len && i<j) { a[j] = a[i]; } } a[i] = key; int pivot = i; if(pivot > begin) quicksort(begin, pivot-1, a, pivot-begin); if(pivot < end) quicksort(pivot+1, end, a, end-pivot); return i; }
运行结果为:
33 22 6 5 7 3 8 9
9 22 6 5 7 3 8
8 3 6 5 7
7 3 6 5
5 3 6
3
6
22
说明递归调用quicksort方法的次数为8次。