<?php/** * 快速排序 */
define("MAX_LENGTH_INSERT_SORT", 7);class QuickSort {    /**     * 交换数组i和j的值     */    function swap(&$data=array(), $i, $j) {        $temp = $data[$i];        $data[$i] = $data[$j];        $data[$j] = $temp;    }    /**     * 交换数组data中子表的记录，是枢轴记录到位，并返回其所在位置     * 左边记录都比枢轴小，右边记录都比枢轴大     * @param array $data 待排序数组     * @param int   $low  底端下标     * @param int   $high 顶端下标     * @return low  枢轴下标位置     */    function PartitionAsc(&$data=array(), $low=0, $high=0) {        $pivotkey=0;        //计算数组中间元素的下标        $m = $low+($high-$low)/2;        //交换左端和右端数据，保证左端较小        if($data[$low]>$data[$high]) {            $this->swap($data, $low, $high);        }        //交换中间和右端数据，保证中间较小        if($data[$m]>$data[$high]) {            $this->swap($data, $high, $m);        }        //获取中间数据，并将中间数据交换到左边        if($data[$m]>$data[$low]) {            $this->swap($data, $m, $low);        }        //用子表的第一个记录作枢轴记录        $pivotkey = $data[$low];        //将枢轴关键字备份到L->r[0]        $data[0] = $pivotkey;        //从表的两端交替地向中间扫描        while($low<$high) {            while ($low<$high && $data[$high]>=$pivotkey) {                $high--;            }            $data[$low] = $data[$high];            while ($low<$high && $data[$low]<=$pivotkey) {                $low++;            }            $data[$high] = $data[$low];        }        $data[$high] = $data[0];        return $low;    }    /**     * 交换数组data中子表的记录，是枢轴记录到位，并返回其所在位置     * 左边记录都比枢轴大，右边记录都比枢轴小     * @param array $data 待排序数组     * @param int   $low  底端下标     * @param int   $high 顶端下标     * @return low  枢轴下标位置     */    function PartitionDesc(&$data=array(), $low=0, $high=0) {        $pivotkey=0;        //计算数组中间元素的下标        $m = $low+($high-$low)/2;        //交换左端和右端数据，保证左端较小        if($data[$low][0]<$data[$high][0]) {            $this->swap($data, $low, $high);        }        //交换中间和右端数据，保证中间较小        if($data[$m][0]<$data[$high][0]) {            $this->swap($data, $high, $m);        }        //获取中间数据，并将中间数据交换到左边        if($data[$m][0]<$data[$low][0]) {            $this->swap($data, $m, $low);        }        //用子表的第一个记录作枢轴记录        $pivotkey = $data[$low];        //将枢轴关键字备份到L->r[0]        $data[0] = $pivotkey;        //从表的两端交替地向中间扫描        while($low<$high) {            while ($low<$high && $data[$high][0]<=$pivotkey[0]) {                $high--;            }            $data[$low] = $data[$high];            while ($low<$high && $data[$low][0]>=$pivotkey[0]) {                $low++;            }            $data[$high] = $data[$low];        }        $data[$high] = $data[0];        return $low;    }    /**     * 快速排序（升序）     * @param array $data 待排序数组     * @param int   $low  底端下标     * @param int   $high 顶端下标     * @return void     */    function QsortAsc(&$data=array(), $low=0, $high=0) {        $pivot=0;        //当high-low大于常数时用快捷排序        if(($high-$low)>MAX_LENGTH_INSERT_SORT) {            while($low<$high) {                //将data一分为二，算出枢轴值pivot                $pivot = $this->PartitionAsc($data, $low, $high);                //对底子表递归排序                $this->QsortAsc($data, $low, $pivot-1);                //尾递归                $low = $pivot+1;            }        } else {            //当high-low小于等于常数时用直接插入排序            $this->InsertSortAsc($data, $low, $high);        }    }    /**     * 快速排序（降序）     * @param array $data 待排序数组     * @param int   $low  底端下标     * @param int   $high 顶端下标     * @return void     */    function QsortDesc(&$data=array(), $low=0, $high=0) {        $pivot=0;        //当high-low大于常数时用快捷排序        if(($high-$low)>MAX_LENGTH_INSERT_SORT) {            while($low<$high) {                //将data一分为二，算出枢轴值pivot                $pivot = $this->PartitionDesc($data, $low, $high);                //对底子表递归排序                $this->QsortDesc($data, $low, $pivot-1);                //尾递归                $low = $pivot+1;            }        } else {            //当high-low小于等于常数时用直接插入排序            $this->InsertSortDesc($data, $low, $high);        }    }    /**     * 插入排序（升序）     */    function InsertSortAsc(&$data=array(), $low=0, $high=0) {        $i=$j=0;        if(0 == $high) {            $length=count($data)-1;        } else {            $length=$high;        }        for($i=$low+1;$i<=$length;$i++) {            if($data[$i][0]<$data[$i-1][0]) {                $data[0]=$data[$i];                for ($j=$i-1; $data[$j][0]>$data[0][0]; $j--) {                     if($j<$low) break;                    $data[$j+1]=$data[$j];                }                $data[$j+1]=$data[0];            }        }    }    /**     * 插入排序（降序）     */    function InsertSortDesc(&$data=array(), $low=0, $high=0) {        $i=$j=0;        if(0 == $high) {            $length=count($data)-1;        } else {            $length=$high;        }        for($i=$low+1;$i<=$length;$i++) {            if($data[$i][0]>$data[$i-1][0]) {                $data[0]=$data[$i];                for ($j=$i-1; $data[$j][0]<$data[0][0]; $j--) {                    if($j<$low) break;                    $data[$j+1]=$data[$j];                }                $data[$j+1]=$data[0];            }        }    }    /**     * 快速排序     * @param array $data 待排序数组     * @param int   $type 1升序 2降序 默认升序     * @return void     */    function Sort($data=array(), $type=1) {        $length = count($data)-1;        if(1==$type) {            $this->QsortAsc($data, 1, $length);        } else if(2==$type) {            $this->QsortDesc($data, 1, $length);        } else {            $this->QsortAsc($data, 1, $length);        }        return $data;    }}/********************************************************///测试10万数组排序//测试数组：array(array(排序数据, 原始数组下标),......)$data = array(array(0,0));$max_len = 100000;for($i=1; $i<$max_len; $i++) {    $data[$i] = array(rand(1,$max_len),$i);}$qs = new QuickSort();//1升序， 2降序$qs->Sort($data,2);$qs->Sort($data,1);