[PHP] 排序和查找算法 - 陶士涵

知乎：冒泡排序（bubble sort）的原理是什么？

 

潘屹峰：

冒泡排序的原理可以顾名思义：把每个数据看成一个气泡，按初始顺序自底向上依次对两两气泡进行比较，对上重下轻的气泡交换顺序（这里用气泡轻、重表示数据大、小），保证轻的气泡总能浮在重的气泡上面，直到最轻的气泡浮到最上面；保持最后浮出的气泡不变，对余下气泡循环上述步骤，直到所有气泡从轻到重排列完毕。

 

Nerd Leo：

在实际项目中应该使用PHP自带的库函数。冒泡和快排要在大数据量下才有明显的性能差异 。在几个常用的小数据排序算法中，冒泡是实际效率最差的，选择排序或插入排序

 

<span style="color: #800080;">$nums</span>=<span style="color: #0000ff;">array</span>(7,2,1,3,4,5,6<span style="color: #000000;">);
</span><span style="color: #800080;">$length</span>=<span style="color: #008080;">count</span>(<span style="color: #800080;">$nums</span><span style="color: #000000;">);
</span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=0;<span style="color: #800080;">$i</span>$length;<span style="color: #800080;">$i</span>++<span style="color: #000000;">){
    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span>=(<span style="color: #800080;">$length</span>-1);<span style="color: #800080;">$j</span>><span style="color: #800080;">$i</span>;<span style="color: #800080;">$j</span>--<span style="color: #000000;">){
        </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$nums</span>[<span style="color: #800080;">$j</span>]$nums[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">]){
            </span><span style="color: #800080;">$temp</span>=<span style="color: #800080;">$nums</span>[<span style="color: #800080;">$j</span><span style="color: #000000;">];
            </span><span style="color: #800080;">$nums</span>[<span style="color: #800080;">$j</span>]=<span style="color: #800080;">$nums</span>[<span style="color: #800080;">$j</span>-1<span style="color: #000000;">];
            </span><span style="color: #800080;">$nums</span>[<span style="color: #800080;">$j</span>-1]=<span style="color: #800080;">$temp</span><span style="color: #000000;">;
        }
    }
}</span>

 

 

知乎：想请教一下学算法的大神，快速排序和二叉树排序哪个快一点？

本人对排序算法了解不多，但是大概知道快速排序和二叉树排序的原理。两者在排序速度上差别大吗？恳请大神给我这个小白科普一下。

 

Yan Gu：

首先，默认题主说串行的情形，我猜题主并不一定知道任何一个并行排序算法。

 

其次，搜索树排序是一个general的概念，默认姑且为“随机二叉搜索树”。用它排序的computational DAG完全等价于快速排序（具体分析自己去看1987年那篇论文），但是虽然计算是完全一样的，计算的顺序却大不相同，因而快排的cache locality要好的多得多（不懂请自行维基），所以会快得多。

 

当然二叉树排序并不是没有优点。他的最大优势就在于并不是swap-based sorting。导致的缺点虽然是memory access pattern的导致有很多random access，但是优点是并不用频繁的写内存，于是在一些特殊setting下是有优势的。（如果蛋疼想知道具体内容，请去我主页把那些关于sorting的paper看了就懂了。）

 

白如冰：

快排和二叉搜索树本质上是一样一样的。

快排的partion不就是分左右子树么。

快速排序：

 

<span style="color: #0000ff;">function</span> quick_sort(<span style="color: #800080;">$array</span><span style="color: #000000;">){
    </span><span style="color: #0000ff;">if</span> (<span style="color: #008080;">count</span>(<span style="color: #800080;">$array</span>) return <span style="color: #800080;">$array</span><span style="color: #000000;">;
    </span><span style="color: #800080;">$key</span>=<span style="color: #800080;">$array</span>[0<span style="color: #000000;">];
    </span><span style="color: #800080;">$left_arr</span>=<span style="color: #0000ff;">array</span><span style="color: #000000;">();
    </span><span style="color: #800080;">$right_arr</span>=<span style="color: #0000ff;">array</span><span style="color: #000000;">();
    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=1;<span style="color: #800080;">$i</span>count(<span style="color: #800080;">$array</span>);<span style="color: #800080;">$i</span>++<span style="color: #000000;">){
        </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$array</span>[<span style="color: #800080;">$i</span>]$key<span style="color: #000000;">){
            </span><span style="color: #800080;">$left_arr</span>[]=<span style="color: #800080;">$array</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">];
        }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{
            </span><span style="color: #800080;">$right_arr</span>[]=<span style="color: #800080;">$array</span>[<span style="color: #800080;">$i</span><span style="color: #000000;">];
        }
        
    }
    </span><span style="color: #800080;">$left_arr</span>=quick_sort(<span style="color: #800080;">$left_arr</span><span style="color: #000000;">);
    </span><span style="color: #800080;">$right_arr</span>=quick_sort(<span style="color: #800080;">$right_arr</span><span style="color: #000000;">);
    </span><span style="color: #0000ff;">return</span> <span style="color: #008080;">array_merge</span>(<span style="color: #800080;">$left_arr</span>,<span style="color: #0000ff;">array</span>(<span style="color: #800080;">$key</span>),<span style="color: #800080;">$right_arr</span><span style="color: #000000;">);
    
}</span>

 

二分查找：

<span style="color: #0000ff;">function</span> bin_sch(<span style="color: #800080;">$array</span>, <span style="color: #800080;">$low</span>, <span style="color: #800080;">$high</span>, <span style="color: #800080;">$k</span><span style="color: #000000;">){
    </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$low</span> $high<span style="color: #000000;">){
        </span><span style="color: #800080;">$mid</span> = <span style="color: #008080;">intval</span>((<span style="color: #800080;">$low</span>+<span style="color: #800080;">$high</span>)/2<span style="color: #000000;">);
        </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$array</span>[<span style="color: #800080;">$mid</span>] == <span style="color: #800080;">$k</span><span style="color: #000000;">){
            </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$mid</span><span style="color: #000000;">;
        }</span><span style="color: #0000ff;">elseif</span> (<span style="color: #800080;">$k</span> $array[<span style="color: #800080;">$mid</span><span style="color: #000000;">]){
            </span><span style="color: #0000ff;">return</span> bin_sch(<span style="color: #800080;">$array</span>, <span style="color: #800080;">$low</span>, <span style="color: #800080;">$mid</span>-1, <span style="color: #800080;">$k</span><span style="color: #000000;">);
        }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{
            </span><span style="color: #0000ff;">return</span> bin_sch(<span style="color: #800080;">$array</span>, <span style="color: #800080;">$mid</span>+1, <span style="color: #800080;">$high</span>, <span style="color: #800080;">$k</span><span style="color: #000000;">);
        }
    }
    </span><span style="color: #0000ff;">return</span> -1<span style="color: #000000;">;
}</span>