這篇文章主要介紹了關於淺談PHP原始碼二十六:PHP快速排序原始碼實現的簡化,有著一定的參考價值,現在分享給大家,有需要的朋友可以參考一下
淺談PHP原始碼二十六:PHP快速排序原始碼實現的簡化
這段時間在複習資料結構,有看到排序及經典的快速排序
於是有了看下PHP中實現排序的方式,在Zend目錄下我們可以看到zend_qsort.c檔案及zend_qsort.h檔案
這是PHP實現快速排序的檔案所在
從程式碼中我們可以看到,也許是為了相容多種數據類型,所以其在交換及比較位置比較複雜,看起來也比較糾結,於是自己將
其中的類型全部換成int類型,得到簡化版本的PHP源碼中的快速排序
其代碼如下:
#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;}
看完後,有一個感覺:強大的指針,受益非淺!
以上就是本文的全部內容,希望對大家的學習有所幫助,更多相關內容請關注PHP中文網!
相關推薦:
淺聊PHP 原始碼二十五:關於next,current,key函數
淺聊PHP原始碼二十四:iterator實作中當值為false時無法完成迭代的原因分析
以上是淺談PHP源碼二十六:PHP快速排序源碼實現的簡化的詳細內容。更多資訊請關注PHP中文網其他相關文章!