排序算法--快速排序

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


        算法描述:

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

  • 从数列中挑出一个元素,称为 “基准”(pivot);

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

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

       动图演示:

    冷暖自知一抹茶ck

        代码实现:

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 

冷暖自知一抹茶ck
请先登录后发表评论
  • 最新评论
  • 总共0条评论