A brief discussion of PHP source code twenty-six: Simplification of PHP quick sort source code implementation

This article mainly introduces the simplification of PHP source code twenty-six: PHP quick sorting source code implementation, which has a certain reference value. Now I share it with you. Friends in need can refer to it

A brief discussion of PHP source code twenty-six: Simplification of PHP quick sort source code implementation

During this period of time, I was reviewing the data structure, and I saw sorting and classic quick sort
So I decided to take a look at the implementation of sorting in PHP In the Zend directory, we can see the zend_qsort.c file and zend_qsort.h file
This is where the file for PHP to implement quick sorting is located
We can see from the code that it may be compatible with a variety of data type, so its exchange and comparison positions are more complicated, and it seems to be more tangled, so I changed all the types in
to int type, and got a simplified version of quick sort in the PHP source code
The code is as follows:

#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;}

After reading this, I have a feeling: powerful pointers are of great benefit!

The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

A brief discussion on PHP source code twenty-five: About next, current, key functions

A brief discussion PHP source code twenty-four: Analysis of the reasons why iteration cannot be completed when the value is false in iterator implementation

The above is the detailed content of A brief discussion of PHP source code twenty-six: Simplification of PHP quick sort source code implementation. For more information, please follow other related articles on the PHP Chinese website!