数据结构和算法——快速排序
1、要解决的问题
给定如下所示的数字列表，请按升序对它们进行排序。
$numbers = [21,25,100,98,89,77];要求
- 对数字进行排序时，需要使用插入
快速算法。 - 用PHP实现该算法
2、伪代码说明
快速排序也是一种分治算法，类似于合并排序。它通过从列表中选择一个元素（轴）并在其左侧放置小于轴的元素，在其右侧放置大于轴的元素来工作。我们对左侧和右侧重复上述步骤，直到无法再划分列表为止。
选择轴可能很棘手，通常我们只使用第一个或最后一个元素。
描述快速排序的伪代码如下：
PROCEDURE function quickSort IF list is empty Return the list END IF Choose first element as the pivot FOR each element of the list start from position 1 IF element is greater than pivot Assign it to the left side ELSE Assign it to the right side END IF END FOR return quickSort(left)+pivot+quickSort(right) END PROCEDURE3、PHP实现快速排序
如我们所见，我们对该算法使用了递归。通常，分治法算法意味着该算法可以递归编写。
<?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)*/作为一种分而治之的算法，快速排序算法确实非常简单。
举报
腾讯云开发者
