PHP源码阅读笔记二十六:PHP快速排序源码实现的简化版本
PHP源码阅读笔记:PHP中的快速排序实现的简化版本
这段时间在复习数据结构,有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式,在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到,也许是为了兼容多种数据类型,所以其在交换及比较位置比较复杂,看起来也比较纠结,于是自己将
其中的类型全部换成int类型,得到简化版本的PHP源码中的快速排序
其代码如下 :
#include
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;
}
看完后,有一个感受:强大的指针,受益非浅!