算法学习八、排序(下)

归并排序的原理

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

递推公式

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))


终止条件:
p >= r 不用再继续分解

代码实现

public function mergeSort($arr)
{
    return $this->mergeSortC($arr, 0, count($arr) - 1);
}


protected function mergeSortC($arr, $start, $end)
{
    if ($start >= $end) {
        return [$arr[$start]];
    }
    // 不加 int 强转,middle 不是整数
    $middle = (int)(($start + $end) / 2);
    // 注意是右边 $middle + 1 而不是左边 $middle - 1
    return $this->merge($this->mergeSortC($arr, $start, $middle), $this->mergeSortC($arr, $middle + 1, $end));
}


protected function merge($arrA, $arrB)
{
    $tmp = [];
    $i = 0;
    $j = 0;
    while (! empty($arrA[$i]) && ! empty($arrB[$j])) {
        if ($arrA[$i] <= $arrB[$j]) {
            $tmp[] = $arrA[$i];
            $i++;
        } else {
            $tmp[] = $arrB[$j];
            $j++;
        }
    }
    if (! empty($arrA)) {
        for (; $i < count($arrA); $i++) {
            $tmp[] = $arrA[$i];
        }
    }
    if (! empty($arrB)) {
        for (; $j < count($arrB); $j++) {
            $tmp[] = $arrB[$j];
        }
    }
    return $tmp;

归并排序的性能分析

归并排序是稳定的排序算法吗?

归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。

在合并的过程中,如果 A[p…q]和 A[q+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定的排序算法。

归并排序的时间复杂度是多少?

如果我们定义求解问题 a 的时间是 T(a),求解问题 b、c 的时间分别是 T(b) 和 T( c),那我们就可以得到这样的递推关系式:

T(a) = T(b) + T(c) + K

其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。

我们假设对 n 个元素进行归并排序需要的时间是 T(n),那分解成两个子数组排序的时间都是 T(n/2)。我们知道,merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是:

T(1) = C; n=1时,只需要常量级的执行时间,所以表示为C。
T(n) = 2*T(n/2) + n; n>1

分解如下:

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

通过这样一步一步分解推导,我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们得到 k=log2n。我们将 k 值代入上面的公式,得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话,T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。

归并排序的空间复杂度是多少?

归并排序的时间复杂度任何情况下都是 O(nlogn),即便是快速排序,最坏情况下,时间复杂度也是 O(n^2)。但是,归并排序并没有像快排那样,应用广泛,因为归并排序不是原地排序算法。归并排序的空间复杂度是 O(n)。

快速排序的原理

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。

我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。

递推公式

递推公式:
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)


终止条件:
p >= r

代码实现

public function quickSort(&$arr)
{
    $this->quickSortC($arr, 0, count($arr) - 1);
}


protected function quickSortC(&$arr, $start, $end)
{
    if ($start >= $end) {
        return;
    }
    $pivot = $this->partition($arr, $start, $end);
    $this->quickSortC($arr, $start, $pivot - 1);
    $this->quickSortC($arr, $pivot + 1, $end);
}


protected function partition(&$arr, $start, $end)
{
    $pivot = $arr[$end];
    $i = $start;
    for ($j = $start; $j < $end; $j++) {
        if ($arr[$j] < $pivot) {
            [$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
            $i++;
        }
    }
    [$arr[$i], $arr[$end]] = [$arr[$end], $arr[$i]];
    return $i;

快速排序的性能分析

快排是一种原地、不稳定的排序算法。

如果每次分区操作,都能正好把数组分成大小接近相等的两个小区间,那快排的时间复杂度递推求解公式跟归并是相同的。所以,快排的时间复杂度也是 O(nlogn)。

但实际上这种情况是很难实现的。我举一个比较极端的例子。如果数组中的数据原来已经是有序的了,比如 1,3,5,6,8。如果我们每次选择最后一个元素作为 pivot,那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作,才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素,这种情况下,快排的时间复杂度就从 O(nlogn) 退化成了 O(n^2)。

T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn),只有在极端情况下,才会退化到 O(n^2)

在 O(n) 复杂度内查找无序数组的第K大元素

我们选择数组区间 A[0…n-1] 的最后一个元素 A[n-1] 作为 pivot,对数组 A[0…n-1] 原地分区,这样数组就分成了三部分,A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1=K,那 A[p] 就是要求解的元素;如果 K>p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间,我们再按照上面的思路递归地在 A[p+1…n-1] 这个区间内查找。同理,如果 K<p+1,那我们就在 A[0…p-1] 区间查找。

public function findKth($arr, $k)
{
    return $this->findKthC($arr, 0, count($arr) - 1, $k);
}


protected function findKthC(&$arr, $start, $end, $k)
{
    $pivot = $arr[$end];
    $i = $start;
    for ($j = $start; $j < $end; $j++) {
        if ($arr[$j] > $pivot) {
            [$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
            $i++;
        }
    }
    [$arr[$i], $arr[$end]] = [$arr[$end], $arr[$i]];
    if ($i + 1 == $k) {
        return $arr[$i];
    } else if ($i + 1 > $k) {
        return $this->findKthC($arr, $start, $i - 1, $k);
    } else {
        return $this->findKthC($arr, $i+1, $end, $k);
    }
}