上一次我说到所谓的“非递归”快速排序算法，不过是用栈来消除了递归，它的运行时间肯定比递归算法长，我们不妨来实际实现一下。代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define MAX_TOP 10000 /*一个很大的栈*/ 6 #define NUM 500L 7 8 /*有关栈的数据结构*/ 9 struct Region { 10 long left; 11 long right; 12 }; 13 14 struct Stack { 15 struct Region reg[MAX_TOP+1]; 16 long top; 17 }; 18 19 /*对栈进行操作的函数*/ 20 void init_stack(struct Stack *s); 21 void push_stack(struct Stack *s, struct Region r); 22 struct Region pop_stack(struct Stack *s); 23 int is_stack_empty(struct Stack *s); 24 25 /*与排序有关的函数*/ 26 27 long partition(double a[], long left, long right); /*划分区间*/ 28 void nr_qsort(double a[], long left, long right); 29 30 31 int main(void) 32 { 33 double a[NUM]; /*待排序数据*/ 34 clock_t t_s, t_e; 35 long i; 36 37 srand(time(NULL)); 38 for (i = 0; i < NUM; ++i) 39 a[i] = rand() % 1000000; 40 41 /*统计运行时间*/ 42 t_s = clock(); 43 nr_qsort(a, 0, NUM-1); 44 t_e = clock(); 45 double t = (t_e - t_s) / (double) CLOCKS_PER_SEC; 46 printf("Non Recursive quick sort %ld items used time: %f s ", NUM, t); 47 48 return 0; 49 } 50 51 52 /*implementation*/ 53 54 void init_stack(struct Stack *s) 55 { 56 s->top = -1; 57 } 58 59 void push_stack(struct Stack *s, struct Region r) 60 { 61 if (s->top == MAX_TOP) { 62 fprintf(stderr, "Stack overflow! "); 63 exit(0); 64 } 65 s->reg[++s->top] = r; 66 } 67 68 struct Region pop_stack(struct Stack *s) 69 { 70 if (s->top == -1) { 71 fprintf(stderr, "Stack underflow! "); 72 exit(0); 73 } 74 return (s->reg[s->top--]); 75 } 76 77 int is_stack_empty(struct Stack *s) 78 { 79 return (s->top == -1); 80 } 81 82 /*返回划分的区间*/ 83 long partition(double a[], long left, long right) 84 { 85 double base = a[left]; /*以最左边的元素作为比较基准*/ 86 87 while (left < right) { 88 while (left < right && a[right] > base) 89 --right; 90 a[left] = a[right]; 91 while (left <right && a[left] < base) 92 ++left; 93 a[right] = a[left]; 94 } 95 a[left] = base; 96 return left; 97 } 98 99 void nr_qsort(double a[], long left, long right) 100 { 101 struct Stack s; 102 struct Region region, regionlow, regionhi; 103 long p; /*记录划分出的分界点*/ 104 105 init_stack(&s); 106 region.left = left; 107 region.right = right; 108 push_stack(&s, region); 109 110 while (!is_stack_empty(&s)) { 111 region = pop_stack(&s); 112 p = partition(a, region.left, region.right); 113 if (p-1 > region.left) { 114 regionlow.left = region.left; 115 regionlow.right = p - 1; 116 push_stack(&s, regionlow); 117 } 118 if (region.right > p + 1) { 119 regionhi.left = p + 1; 120 regionhi.right = region.right; 121 push_stack(&s, regionhi); 122 } 123 } 124 125 }
在代码的第110行至第122行的while循环中，做的正是用栈消除递归的工作。想想递归的算法中，把划分好的左右区间界限（即left,right）保存到了系统管理的栈中，这里手动把每次划分出来的区间分界保存至栈中，当第113和118行的两个条件不满足时，所在区间的元素都是有序的状态，此时不进行压栈操作而向前返回（即递归的回调）。关于用栈消除递归的算法可以参考关于数据结构的书籍，比如陈锐的《零基础学数据结构》有关栈的那一章就有介绍。实际运行两个程序的结果如下：
$ ./nr_qsort #非递归算法的快排 Non Recursive quick sort 500 items used time: 0.000261 s $ ./qsort #递归算法的快排 Quick sort 500 items used time:0.000104 s
之所以只用了500个数据，是因为超过1000个数据后，非递归快排的速度就慢的令人难以忍受。下面是另外两次关于递归算法快排的测试：
$ time ./qsort Quick sort 1000000 items used time:0.289171 s real 0m0.372s user 0m0.332s sys 0m0.012s #下面更改NUM即数据的个数为10000000 $ ./qsort Segmentation fault #超出栈的大小 $ ulimit -s unlimited #更改栈的大小为不受限 $ time ./qsort Quick sort 10000000 items used time:3.259025 s #成功进行了排序 real 0m4.044s user 0m3.740s sys 0m0.172s
这也印证了上一次谈到的系统默认限制带来的问题。