算法-经典排序算法(Ⅱ)

发表于   |   分类于   |  

最近又学了经典的几个 『O(n㏒n)』 复杂度的算法比较。主要是 快速排序、归并排序、以及寻找第K大数，寻找第K小数

在坑了几天后，终于明白了如何 利用快速排序在O(n)复杂度 内实现寻找第K大数或者第K小数。不得不说思维的转变真的很重要，一直都没绕过来…

快速排序

快速排序：Quick Sort

又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，时间复杂度为 O(n㏒n),最坏情况下时间复杂度为O(n²).核心思想是使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列

排序过程：

1.寻找基准值。快速排序是可以在待排序的数据中选取任意一点作为基准值的，不过一般我们都是选取头或尾的结点为基准值。

2.找到基准值后开始进行分割。将待排序的数据依依和基准值比较，值小于基准的放到前面，值大于基准的放到后面（PS：这里大小值分别放前还是后都是可以的）。这样操作下来就会得到3个区间，前面一个区间的值都是小于基准值的假设我们叫它 Before区间，然后中间是基准值假设我们叫它 Pivot区间，然后后面就都是大于基准值的区间假设我们叫它 After区间。形如下图：

pivot

3.然后分别对Before区间和After区间重复第一步和第二步操作，直到待排序的区间大小是0或者1的时候结束，此时待排序的数组显然已经是有序的了

从上面可以看出这是一个重复的操作，可以通过递归来实现。要实现递归需要找到2个东西，第一找到递推公式，第二找到退出条件。

1
2
3
4
5
递推公式：
quickSort(array) = quickSort(before_array) + pivot_array + quickSort(after_array);
退出条件：
count(array) <= 1

有了递归的条件下面是PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function quickSort($arr)
{
    $count = count($arr);
    if ($count <= 1) {
        return $arr;
    }
    // 假设最后一个结点为枢纽
    $pivot = $arr[$count - 1];
    $before = [];
    $after = [];
    for ($i = 0; $i < $count - 1; $i++) {
        if ($arr[$i] <= $pivot) {
            $before[] = $arr[$i];
        } else {
            $after[] = $arr[$i];
        }
    }
    return array_merge(quickSort($before), [$pivot], quickSort($after));
}
$arr = [
    3, 7, 8, 5, 2, 1, 9, 5, 4
];
$nums = quickSort($arr);
var_dump($nums);
exit();

快速排序的改进

上面已经初步实现了快速排序，但是这不是很理想。因为每次递归都需要开辟 before 和 after 两块额外的数组空间，而且使用了 array_merge 函数。这样在实际的实现上其实是会极度影响速度和缓存的性能，同时也会导致快速排序不再是一个原地排序算法（空间复杂度为O(1)的算法叫原地排序算法）。

如果要改进快速排序为原地排序就需要把他的空间复杂度降低到O(1),那也就是要实现找基准点分区那一块的操作不能占用太多的额外空间，需要在原地完成找基准和分区。

在实现上有些类似选择排序的思想和数组实现O(1)复杂度内元素插入操作。找一个基准值，把待分区的数据想象成2个区间，前面的区间放比基准值小的数据，那么后面的区间就是待比较的数据，然后每次从待比较的区间中取出一个值和基准比较，小于等于基准的话就放到前面的区间末尾，大于的话就不动，接着取下一个值。这样只需要依次把所有数据走完一轮比较就可以找到基准值应该存在的位置了。

实现过程：

1.找到一个基准值，一般选择最后一个值或者第一个值，假设我们选择最后一个值作为基准
2.使用2个下标来控制已比较区间和待比较区间，假设2个下标分别是 i 和 j 开始的时候都指向下标0，前面放的都是小于基准的值，那此时已比较区间其实是空的，因为还没开始比较。而 i 其实相当于一个分隔符，隔开了已比较区间和待比较区间，它紧跟在已比较区间的后面。这里一定要想清楚。
3.依次移动 j 取值和基准比较，如果小于基准把 i 下标的值和 j 下标的值进行交换，然后把 i++，因为 i 是紧跟在已比较区间的后面的，当 i 位置换来了一个小于基准的值，相当于给已比较区间增加了一个元素，那么 i 就需要自增1才能紧跟在已比较区间的后面。
4.这样一直走完所有数据比较，可以确定 i 之前的值都是小于基准的，但是 i 位置上的值是不确定的，可能大于或者小于基准值，所以我们要把不确定的 i 下标的值和基准值换过来（对应上面的话也就是 i 下标的值和待排序数据的最后一位的值，因为上面基准取的是最后一位）。此时返回的 i 就是基准值应该出现的位置。

大概如下图：

partition

PHP实现伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function partition(&$arr, $begin, $end)
{
    // 假设最后一个为枢纽
    $pivot = $arr[$end];
    // 设置起点
    $i = $j = $begin;
    for ($j; $j < $end; $j++) {
        if ($arr[$j] < $pivot) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;
            ++$i;
        }
    }
    $tmp = $arr[$i];
    $arr[$i] = $arr[$end];
    $arr[$end] = $tmp;
    return $i;
}

有了分区操作的优化后，在来优化下快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$arr = [
    3, 7, 8, 5, 2, 1, 9, 5, 4
];
function quickSort(&$arr, $begin, $end)
{
    if ($begin >= $end) {
        return $arr;
    }
    // 上面的改进分区方法
    $index = partition($arr, $begin, $end);
    quickSort($arr, $begin, $index - 1);
    quickSort($arr, $index + 1, $end);
}
// 调用
quickSort($arr, 0, count($arr) - 1);
var_dump($arr);
exit();

快速排序总结：

1.执行效率：快速排序的最好情况时间复杂度是 O(n㏒n),就是在每次都可以把待排序的数据正好分成两个大小相等的区间，这时每次递归都是求一半区间。最坏情况时间复杂度是 O(n²) 也就是在每次分区都得到 两个大小不均匀的区间，比如 5, 4, 3, 2, 1。需要进行大约 n 次分区操作，每次分区平均需要遍历大约 n/2 个元素，根据 (n * n / 2) 去掉常量，快速排序的时间复杂度就从 O(n㏒n) 退化成了 O(n²)。 平均情况时间复杂度是 O(n㏒n)

2.内存消耗：一般我们都是选择使用上面那种优化过的分区操作，所以他的空间消耗是常量级别的 O(1)。

3.稳定性：如果选择上面的优化过的分区操作，快速排序就是一个不稳定的算法了，一般我们说它不稳定也是来源于此。比如 7, 9, 7, 6 在第一次分区后第一个7就换到了末尾，所以是不稳定的算法。如果不考虑空间消耗使用第一种分区应该就是稳定算法了，一般不推荐这么干。

实现在O(n)复杂度内寻找第K大/小数

还有一个很常见的算法，要求出一组无序数据中的第K大数，或者第K小数。假设我们现在需要寻找第K大的数据。举个例子：在数据 3, 7, 8, 5, 2, 1, 9, 5, 4 中，第一大数就是9，第二大就是8，第三大就是7. 如何找到呢？当然可以暴力求解，比如每次找到其中的最大值放到数据的最前面，然后重复K次就找到了第K大的数。根据时间复杂度考量这种方法的时间复杂度是 O(k * n),忽略掉常量K就是O(n)了，但是当K是 n / 2 或者是 n 的时候，复杂度就变为了 O(n²)

要实现在 O(n) 复杂度内寻找K大数，可以借助优化快速排序的分区方法，有点不同的是把大于基准的数放到前面。

实现过程：

1.借助O(n) 复杂度的分区，大于基准的值放前面，然后返回当前的基准元素的下标 假设是 index。这样的话数组就被分为了3块区域。基准下标前面的数据都是大于基准的，然后是基准值，后面是小于基准的数据。而数据是从下标0开始算的，所有当前基准值的 下标 + 1 就是 第 (index + 1) 大数（PS:这里有个点需要绕过来,现在数据变成了前面一个区间都是大于基准的值，然后基准的下标是index，数据的下标从0开始，从左向右数过来，那index下标对应的值不就是 第 （index+1） 大的数了吗）。如下图：

findk

返回的下标 index = 5 说明当前的基准是 5 + 1 = 6 也就是第六大的数。

2.进行判断。如果 index + 1 == K 说明当前的下标 index 对应的值就是第K大数。因为下标从0开始的，+1才回到正常。如果 index + 1 < K 说明第K大的数在 下标 index + 1 到 end 之间（为什么？index+1 < k 说明当前的下标落在了前面的区间，那只能继续向基准后面的区间继续查找。）; 如果 index + 1 > K 说明第K大数在下标 begin 到 index - 1 之间，index前一个不就是减1嘛（同上面）！

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function partition(&$arr, $begin, $end)
{
    // 假设最后一个为枢纽
    $pivot = $arr[$end];
    // 设置起点
    $i = $j = $begin;
    for ($j; $j < $end; $j++) {
        if ($arr[$j] > $pivot) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;
            ++$i;
        }
    }
    $tmp = $arr[$i];
    $arr[$i] = $arr[$end];
    $arr[$end] = $tmp;
    return $i;
}
function findKth(&$arr, $k, $begin, $end)
{
    $index = partition($arr, $begin, $end);
    if ($index + 1 == $k) {
        return $arr[$index];
    }
    if ($index + 1 < $k) {
        return findKth($arr, $k, $index + 1, $end);
    } else {
        return findKth($arr, $k, $begin, $index - 1);
    }
}
$arr = [
    3, 7, 8, 5, 2, 1, 9, 5, 4
];
$k_th = 3;
$k_value = findKth($arr, $k_th, 0, count($arr) - 1);
var_dump($k_value);

如果求第K小的值，只需要把分区的函数的if判断改成小于，小值在前即可。

通过上面的分析可以得出第一轮需要遍历n个元素，第二轮就是 n/2 个元素，第三轮就是 n/4 个元素然后以此类推， n/8, n/16 直到区间缩小为1。然后把每次分区遍历的元素个数加起来就变成了 n+ n/2 + n/4 + n/8 ... + 1 最后的和是 2n - 1 忽略掉常量所以复杂度就变为 O(n) 了。

归并排序

归并排序：Merge Sort. 该算法需要经过2步

分割：递归的把当前的数据分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列合并到一起。

排序过程：

1.从中间把待排序的数据分成左右两半
2.然后分别对两部分进行第一步操作，继续分，分到只有小于等于1个元素的时候开始准备排序合并
3.把左右两部分排序合并，递归合并回来就完成了排序

动图如下：

merge_sort

PHP实现伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function mergeSort($arr)
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    $left = mergeSort($left);
    $right = mergeSort($right);
    $arr = myMerge2($left, $right);
    return $arr;
}
function myMerge($left, $right)
{
    $tmp = [];
    
    // 循环比较 直到左右都还有元素的时候
    // 谁没有元素了就是谁被取空了
    while (count($left) && count($right)) {
        $tmp[] = $left[0] > $right[0] ? array_shift($right) : array_shift($left);
    }
    // 当比较完后其中之一还会有剩余 而且是排序好的
    // 前面的tmp中肯定都是小的有序，所以合并进来剩余的
    return array_merge($tmp, $left, $right);
}

上面的写法有些偷懒，其中的关键点在于合并的函数 也就是上面的 myMerge() 函数，就是把2个有序的数组合并成一个有序的数组。

可以这样实现：假设待合并的2个数组是 left 和 right, 首先本身这2个数组的元素已经是有序的了。

然后使用了一个临时的空数组 tmp 做为存储。

使用游标 i 和 j 分别指向 left 和 right 的第一个元素，然后比较 left[i] 和 right[j], 如果 left[i] < right[j], 就把 left[i] 放入临时数组 tmp 中,然后 i 下标后移一位, 否则将 right[j] 放入 tmp,然后将 j 后移一位。

重复上面的步骤，直到其中之一的数组都放入了临时数组中，此时再将另外一个数组中的数据全部放入临时数组的末尾即可，就完成了合并操作。

大概伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function myMerge2($left, $right)
{
    $tmp = [];
    $start = 0;
    $i = 0;
    $j = 0;
    $end = $i > $j ? $j : $i;
    while ($i < count($left) && $j < count($right)) {
        // 注意++的使用
        if ($left[$i] <= $right[$j]) {
            $tmp[] = $left[$i++];
        } else {
            $tmp[] = $right[$j++];
        }
    }
    // 当有一个遍历完后i 和 j肯定不相等
    // 判断哪个中还有剩余
    // 先假设left 还有剩余 那么start 和 end如下
    $start = $i;
    $end = count($left);
    $arr = $left;
    // 如果j有剩余就覆盖上面初始化的值
    if ($j < count($right)) {
        $start = $j;
        $end = count($right);
        $arr = $right;
    }
    // 说明有剩余
    while ($start < $end) {
        $tmp[] = $arr[$start++];
    }
    return $tmp;
}

归并排序总结：

1.执行效率：归并排序的时间复杂度与原始数据的有序度没有关系，他的复杂度是很稳定的，最好，最坏，平均时间复杂度都是 O(n㏒n).

2.内存消耗:归并排序在合并2个有序的数组为一个有序数组的时候，需要额外的存储空间。尽管每次操作合并都需要申请额外的存储空间，但是在合并完成后，临时开辟的内存空间是会被释放掉的。在任意时刻 CPU只会有一个函数在执行，也就是只会有一个临时空间在使用。而临时空间最大也就是待排序的数组的数量，也就是最大为 n 个，所以归并排序的空间复杂度为 O(n)

3.稳定性：归并排序稳定不稳定主要是看那个合并的函数，如果有相等的元素可以先把左边数组的元素先放入临时数组中这样就保证了稳定性，所以归并排序是稳定的算法

总结

最好复杂度 最坏复杂度 平均复杂度 空间复杂度 算法稳定性
归并排序 O(n㏒n) O(n㏒n) O(n㏒n) O(n) Yes
快速排序 O(n㏒n) O(n²) O(n㏒n) O(1) No

尽快归并排序的时间复杂度是如此稳定，一直都是 O(n㏒n), 而快速排序在最坏的情况下也有 O(n²), 但是归并排序却没有快速排序使用的广泛，是因为归并排序的空间消耗太多，它不是一个原地排序算法！

-------------The End-------------