排序算法--快速排序

        快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

        算法描述:

        快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

       动图演示:

        代码实现:

function quickSort($arr) {
    $length = count($arr);    
    if($length <= 1) {        //!!!!!!!先判断是否需要继续进行，跳出!!!!!!!
        return $arr;
    }

    //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
    //初始化两个数组
    $base_num    = $arr[0];    //选择第一个元素作为基准
    $left_array  = array();
    $right_array = array();

    for($i=1; $i<$length; $i++) {    //!!!!!!!从1开始，count($arr)长度!!!!!!!
        if( $arr[$i] < $base_num) {
            $left_array[] = $arr[$i];
        } else {
            $right_array[] = $arr[$i];
        }
    }

    $left_array  = quickSort($left_array);
    $right_array = quickSort($right_array);

    return array_merge($left_array, array($base_num), $right_array);
}

维基百科：https://en.wikipedia.org/wiki/Quicksort 

本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn

• 上一篇： PHP读取word docx文档内容及处理图片
• 下一篇： 排序算法--归并排序