PHP源码阅读笔记：PHP中的快速排序实现的简化版本
这段时间在复习数据结构，有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式，在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到，也许是为了兼容多种数据类型，所以其在交换及比较位置比较复杂，看起来也比较纠结，于是自己将
其中的类型全部换成int类型，得到简化版本的PHP源码中的快速排序
其代码如下 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | #include <stdio.h> static qsort_swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; } void qsort(int *base, int nmemb) { int *begin_stack[10]; int *end_stack[10]; int *begin; int *end; int *seg1; int *seg2; int *seg2p; int loop; unsigned int offset; /* 使用栈而不是常见的递归实现 */ begin_stack[0] = base; // 开始元素位置栈，入栈 end_stack[0] = base + (nmemb - 1) ; // 结束位置栈，入栈 for (loop = 0; loop >= 0; --loop) { begin = begin_stack[loop]; // 开始位置出栈 end = end_stack[loop]; // 结束位置出栈 while (begin < end) { offset = (end - begin) >> 1; // 取中间位置 qsort_swap(begin, begin + offset); // 交换开始和中间的位置 seg1 = begin; seg2 = end; while (1) { for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1); for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1); if (seg1 >= seg2) break; qsort_swap(seg1, seg2); } qsort_swap(begin, seg2); seg2p = seg2; if ((seg2p - begin) <= (end - seg2p)) { if (seg2p < end) { // 右侧入栈 begin_stack[loop] = seg2p + 1; end_stack[loop++] = end; } end = seg2p; } else { if (seg2p > begin) { // 左侧入栈 begin_stack[loop] = begin; end_stack[loop++] = seg2p - 1; } // end if begin = seg2p; } // end if } // end while } // end for } int main(int argc, char *argv[]) { int a[10] = {14, 5, 7, 8, 2, 4, 55, 3}; int i; qsort(a, 8); for (i = 0; i < 8;i++) { printf("%d ", a[i]); } return 0; } |
看完后，有一个感受：强大的指针，受益非浅！