算法研究之快速排序
作者 斯人 | 发布于 2012 年 3 月 9 日
PHP PHP内核

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
以上摘自百度百科.
最坏时间复杂度:
O(n二次方);
最好时间复杂度:
O(n);
快速排序的基本思想
1.分解:
在D[i…j…n]的数据中,找一个基准点D[j],将数据划分成左右两份,
左等于D[i…j-1]
右等于D[j+1…n]
2.求解
递归调用划分函数 对左右区间两个数据划分求解.
3.合并左右两个排序好的数据
可见快速排序算法时间复杂度等于划分所花费的时间.
下面详细说一说关键的第二部 求解

划分步骤
数据 D[low…high];
① 设两个变量 i,j,分别指向数据的low 和high.取其中任意一个数据为基准pivot.
② 从右向左移动j,查找比pivot小的数据,找到后将j所指向的数据赋给i,D[i]=D[j]
从左向右移动i,查找比pivot大的数据,找到后将i所指向的数据赋给j.D[j]=D[i];
以此类推不断交换方向,知道i=j的时候停止.这个时候i的位置就是基准pivot所在的位置.

下面通过数据走一遍这个流程
引文用文字不好描述..所以我在本子上用笔画出来..
本人写字不好看..勿喷..^.^


PHP写的代码

function quick_sort(&$array,$x,$y) {
    $i = $x;
    $j = $y;
    $key = $array[$x]; //基准
    while ($i != $j) {
        //$j-- 查找比基准$key小的值
        while ($i < $j && $array[$j] >= $key) {
            $j--;
        }
        //  if($i < $j)
        $array[$i] = $array[$j];
        //$i++查找比基准$key大的值
        while ($i < $j && $array[$i] <= $key) {
            $i++;
        }
        // if($i < $j)
        $array[$j] = $array[$i];
    }
    $array[$i] = $key;
    if($x<$i-1)  //左区间的数据
        quick_sort($array,$x,$i-1);
    if($y>$i+1)//右区间的数据
        quick_sort($array,$i+1,$y);
}
原文出处:http://www.imsiren.com/archives/348