写点什么

归并排序与快速排序以及 PHP 实现

发布于: 2021 年 03 月 14 日
归并排序与快速排序以及PHP实现

一、分治思想

  1. 分治思想:分治,顾明思意,就是分而治之,将一个大问题分解成小的子问题来解决,小的子问题解决了,大问题也就解决了。

  2. 分治与递归的区别:分治算法一般都用递归来实现的。分治是一种解决问题的处理思想,递归是一种编程技巧。

二、归并排序


算法原理

先把数组从中间分成前后两部分,然后对前后两部分分别进行排序,再将排序好的两部分合并到一起,这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢?写递归代码的技巧就是分写得出递推公式,然后找到终止条件,最后将递推公式翻译成递归代码。递推公式怎么写?如下

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

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

性能分析

  1. 算法稳定性:

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

  1. 时间复杂度:分析归并排序的时间复杂度就是分析递归代码的时间复杂度

如何分析递归代码的时间复杂度?

递归的适用场景是一个问题 a 可以分解为多个子问题 b、c,那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后,我们再把 b、c 的结果合并成 a 的结果。若定义求解问题 a 的时间是 T(a),则求解问题 b、c 的时间分别是 T(b)和 T(c),那就可以得到这样的递推公式:T(a) = T(b) + T(c) + K,其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。这里有一个重要的结论:不仅递归求解的问题可以写成递推公式,递归代码的时间复杂度也可以写成递推公式。套用这个公式,那么归并排序的时间复杂度就可以表示为:

		T(1) = C; #n=1 时,只需要常量级的执行时间,所以表示为 C。
T(n) = 2*T(n/2) + n; #n>1,其中n就是merge()函数合并两个子数组的的时间复杂度O(n)。
T(n) = 2*T(n/2) + n
= 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3*n
= 8(2T(n/16) + n/8) + 3n = 16T(n/16) + 4*n
......
= 2^k T(n/2^k) + k n
......
复制代码


T(n/2^k)=T(1) 时,也就是 n/2^k=1,我们得到 k=log2n。将 k 带入上面的公式就得到T(n)=Cn+nlog2n。如用大 O 表示法,T(n)就等于O(nlogn)。所以,归并排序的是复杂度时间复杂度就是O(nlogn)

  1. 空间复杂度:归并排序算法不是原地排序算法,空间复杂度是 O(n)

为什么?因为归并排序的合并函数,在合并两个数组为一个有序数组时,需要借助额外的存储空间。为什么空间复杂度是 O(n)而不是 O(nlogn)呢?如果我们按照分析递归的时间复杂度的方法,通过递推公式来求解,那整个归并过程需要的空间复杂度就是 O(nlogn),但这种分析思路是有问题的!因为,在实际上,递归代码的空间复杂度并不是像时间复杂度那样累加,而是这样的过程,即在每次合并过程中都需要申请额外的内存空间,但是合并完成后,临时开辟的内存空间就被释放掉了,在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时空间再大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。

实现

    /**     * 归并排序     * @param array $a     */    public function mergeSort(array $array)    {        $low = 0;        $n = count($array);        $this->mergeSortRecursive($array, $low, $n - 1);    }
private function mergeSortRecursive(array $array, $low, $high) { // 递归终止条件 if ($low >= $high) { return [$array[$high]]; } // 取中间位置$mid $mid = $low + (($high - $low) >> 1); // 递归,合并 return $this->merge($this->mergeSortRecursive($array, $low, $mid), $this->mergeSortRecursive($array, $mid + 1, $high)); }
private function merge(array $leftArr, array $rightArr) { // 归并排序中最有意思的部分:可以延伸考多个有序数组合并问题 $newArr = []; $leftIndex = $rightIndex = 0;
$leftCount = count($leftArr); $rightCount = count($rightArr);
while ($leftIndex < $leftCount && $rightIndex < $rightCount) { $newArr[] = $leftArr[$leftIndex] <= $rightArr[$rightIndex] ? $leftArr[$leftIndex++] : $rightArr[$rightIndex++]; } // 这里要考虑,如果拼接完成后,数组还有剩余的处理 $start = $leftIndex; $end = $leftCount; $corpArr = $leftArr; if ($rightIndex < $rightCount) { $start = $rightIndex; $end = $rightCount; $corpArr = $rightArr; } while ($start < $end) { $newArr[] = $corpArr[$start++]; } return $newArr; }
复制代码

三、快速排序

算法原理

快排的思想是这样的:如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。然后遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 povit 放到中间。经过这一步之后,数组 p 到 r 之间的数据就分成了 3 部分,前面 p 到 q-1 之间都是小于 povit 的,中间是 povit,后面的 q+1 到 r 之间是大于 povit 的。根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。

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

终止条件:p >= r

性能分析

  1. 算法稳定性:

因为分区过程中涉及交换操作,如果数组中有两个 8,其中一个是 pivot,经过分区处理后,后面的 8 就有可能放到了另一个 8 的前面,先后顺序就颠倒了,所以快速排序是不稳定的排序算法。比如数组[1,2,3,9,8,11,8],取后面的 8 作为 pivot,那么分区后就会将后面的 8 与 9 进行交换。

  1. 时间复杂度:最好、最坏、平均情况

快排也是用递归实现的,所以时间复杂度也可以用递推公式表示。

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

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

T(n) = 2*T(n/2) + n; n>1

所以,快排的时间复杂度也是 O(nlogn)。

如果数组中的元素原来已经有序了,比如 1,3,5,6,8,若每次选择最后一个元素作为 pivot,那每次分区得到的两个区间都是不均等的,需要进行大约 n 次的分区,才能完成整个快排过程,而每次分区我们平均要扫描大约 n/2 个元素,这种情况下,快排的时间复杂度就是 O(n^2)。

前面两种情况,一个是分区及其均衡,一个是分区极不均衡,它们分别对应了快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均时间复杂度是多少呢?T(n)大部分情况下是 O(nlogn),只有在极端情况下才是退化到 O(n^2),而且我们也有很多方法将这个概率降低。

  1. 空间复杂度:快排是一种原地排序算法,空间复杂度是 O(1)

原地交换的实现图解


实现

   /**     * 快排     * @param array $array     * @return array     */    public function quickSort(array $array)    {        $count = count($array);        $this->quickSortRecursive($array, 0, $count - 1);        return $array;    }
private function quickSortRecursive(array &$array, int $left, int $right) { if ($left >= $right) { return; } $q = $this->partition($array, $left, $right); $this->quickSortRecursive($array, $left, $q - 1); $this->quickSortRecursive($array, $q + 1, $right); }
private function partition(array &$array, int $left, int $right) { $pivot = $array[$right]; $index = $left;
for ($j = $left; $j < $right; ++$j) { if ($array[$j] < $pivot) { $tmp = $array[$j]; $array[$j] = $array[$index]; $array[$index] = $tmp; $index ++; } } $tmp = $array[$index]; $array[$index] = $array[$right]; $array[$right] = $tmp;
return $index; }
复制代码


四、归并排序与快速排序的区别

归并和快排用的都是分治思想,递推公式和递归代码也非常相似,那它们的区别在哪里呢?

  1. 归并排序,是先递归调用,再进行合并,合并的时候进行数据的交换。所以它是自下而上的排序方式。何为自下而上?就是先解决子问题,再解决父问题。

  2. 快速排序,是先分区,在递归调用,分区的时候进行数据的交换。所以它是自上而下的排序方式。何为自上而下?就是先解决父问题,再解决子问题。


发布于: 2021 年 03 月 14 日阅读数: 14
用户头像

多读书多看报,少吃零食多睡觉 2018.08.07 加入

还未添加个人简介

评论

发布
暂无评论
归并排序与快速排序以及PHP实现