首页 / 软件开发 / 数据结构与算法 / 如何实现快速排序算法

<？php/** 快速排序算法 * 1. 在数组中找一个元素作为key,一般取数组第一个元素作为key * 2. i=0, j=数组长度-1 * 3. j-- 当 arr[j]<key, arr[i]与arr[j]交换位置 * 4. i++ 当 arr[i]>key, arr[i]与arr[j]交换位置 * 5. 重复3,4 直到 i==j 时,完成。 * 6. 将key分隔的左右两组元素再分别执行 1,2,3,4,5 （递归）。 */$arr = array（）;// 创建数组// for（$i=0; $i<20; $i++）{array_push（$arr, mt_rand（1,200））;}echo "source arr:".implode（",", $arr）."<br>";quicksort（$arr, 0, count（$arr）-1）;echo "sorted arr:".implode（",", $arr）;// 快速排序function quicksort（&$arr, $low, $high）{if（$low>=$high）{return ;}$i = $low;$j = $high;$flag = 1; // 0:i动作 1:j动作$key = $arr[$low];while（$i<$j）{switch（$flag）{case 0: // iif（$arr[$i]>$key）{$tmp = $arr[$i];$arr[$i] = $arr[$j];$arr[$j] = $tmp;$flag = 1;}else{$i++;}break;case 1: // jif（$arr[$j]<$key）{$tmp = $arr[$i];$arr[$i] = $arr[$j];$arr[$j] = $tmp;$flag = 0;}else{$j--;}break;}}// left arrquicksort（$arr, $low, $i-1）;// right arrquicksort（$arr, $i+1, $high）;}？>