快速排序
思路：
我们首先要找到一个基准，数组的前半部分是比基准小的元素，数组后半部分是比基准大的元素，这里我就拿数组第一个元素作为基准； 设置队首和队尾两个指针； 队尾指针先进行活动，一直向队首移动，直到找到比基准值小的元素，然后将这个值赋给队首指针处； 下面队首指针开始活动，一直向队尾移动，直到找到比基准值大的元素，然后将这值赋给队尾指针处； 等到队首指针和队尾指针指向同一处时，将基准值赋给当前指针指向的同一位置，此时，基准元素前面的都是比它要小的元素，后面都是比它大的元素；接下来，就是采用上述步骤将两边的部分分别进行排序，如此循环下去，直至开始的low>=开始的high,说明就剩下了一个元素，也就无需再排了。 /** * @param $arr * @param $low * @param $high * @return mixed */ function quickSort(&$arr,$low,$high){ if($low < $high){ $index = getIndex($arr,$low,$high); quickSort($arr,0,$index-1); quickSort($arr,$index+1,$high); } return $arr; } /** * @param $arr * @param $low * @param $high * @return mixed */ function getIndex(&$arr,$low,$high){ $tmp = $arr[$low]; while($low < $high){ //如果队尾元素值大于基准元素，那么high-- while($low < $high && $arr[$high] > $tmp){ $high--; } //如果队尾元素小于基准值，那么就将队尾元素赋值给队首元素 $arr[$low] = $arr[$high]; //如果队首元素小于基准值，那么low++ while($low < $high && $arr[$low] < $tmp){ $low++; } //如果队首元素大于基准值，就将队首元素赋值给队尾元素 $arr[$high] = $arr[$low]; } //退出时，high == low $arr[$low] = $tmp; return $low; } $arr = array(4,5,1,6,2,8,3,11,10); print_r(quickSort($arr,0,count($arr)-1));
