MENU

常用排序算法实现(2):快速排序

January 31, 2020 • 数据结构与算法

思路:

快速排序采用分治的思想,具体步骤:

  1. 从数组中选取一个基准元素 $pivot;
  2. 将数组中的小于 $pviot 的元素放在 $left 数组,大于 $pvoit 的元素放在 $right 数组;
  3. 按步骤 2 递归处理 $left$right 数组;
  4. 合并 $left[$pviot]$right 数组;

实现:

function quickSort(array $nums)
{
    $len = count($nums);

    if ($len <= 1) {
        return $nums;
    }

    $pivot = $nums[0];
    $left = [];
    $right = [];

    for ($i = 1; $i < $len; $i++) {
        if ($pivot > $nums[$i]) {
            $left[] = $nums[$i];
        } else {
            $right[] = $nums[$i];
        }
    }

    $left = quickSort($left);
    $right = quickSort($right);

    return array_merge($left, [$pivot], $right);
}

时间复杂度为 O(lgn)

Last Modified: February 4, 2020