快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
算法描述:
快速排序使用分治法来把一个串(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