数据结构和算法——快速排序
1、要解决的问题
给定如下所示的数字列表，请按升序对它们进行排序。
$numbers = [21,25,100,98,89,77];要求
对数字进行排序时，需要使用插入
快速算法。用PHP实现该算法
2、伪代码说明
快速排序也是一种分治算法，类似于合并排序。它通过从列表中选择一个元素（轴）并在其左侧放置小于轴的元素，在其右侧放置大于轴的元素来工作。我们对左侧和右侧重复上述步骤，直到无法再划分列表为止。
选择轴可能很棘手，通常我们只使用第一个或最后一个元素。
描述快速排序的伪代码如下：
PROCEDURE function quickSortIF list is emptyReturn the listEND IFChoose first element as the pivotFOR each element of the list start from position 1IF element is greater than pivotAssign it to the left sideELSEAssign it to the right sideEND IFEND FORreturn quickSort(left)+pivot+quickSort(right)END PROCEDURE
3、PHP实现快速排序
如我们所见，我们对该算法使用了递归。通常，分治法算法意味着该算法可以递归编写。
$arrayToSort = [21, 25, 100, 98, 89, 77];function quickSort($data){if (count($data) == 0) {return $data;}$pivot = $data[0];$left = $right = [];for ($i = 1; $i < count($data); $i++) {if ($data[$i] < $pivot) {$left[] = $data[$i];} else {$right[] = $data[$i];}}return array_merge(quicksort($left), array($pivot), quicksort($right));}print_r(quickSort($arrayToSort));// Output:/*Array([0] => 21[1] => 25[2] => 77[3] => 89[4] => 98[5] => 100)*/
作为一种分而治之的算法，快速排序算法确实非常简单。