上篇文章中咱们好好地学习了一下插入类相干的两个排序，不过，和替换类的排序比照的话，它们真的只是弟弟。甚至能够说，在所有的排序算法中，最闻名的两个排序都在明天要介绍的替换排序中了。不论是冒泡、还是快排，都是面试中的常见排序算法，常见到什么境地呢？凡是学习数据结构和算法，甚至是你齐全没有学习过，也多少都会据说过这两个排序算法。而一些大中型公司更是间接在面试题中指明不要应用这两种算法来实现一些排序的题目，这又是为什么呢？那当然也是因为这两个算法切实是太闻名了，很多人都轻易就能手写进去。

当然，不论你面试的公司有什么要求，只有是有志在编程开发这个行业里倒退的同学，冒泡和快排必定会是面试中绕不开的一个坎。咱们明天就来好好地学习一下这两个排序算法。不过首先还是要搞明确这个“替换”指的是什么意思。

上篇文章中的插入排序，指的是间接将数据插入到指定的地位。而替换的意思，则是让两个地位的数据在进行比对后间接替换。比方咱们有 [3, 1, 2] 这样一个数组，须要排列成 [1, 2, 3] 这种模式。那么咱们就能够先让 3 和 1 比拟，发现 1 小，于是将 3 和 1 的地位进行替换，后果是 [1, 3, 2]。而后再让 3 和 2 比拟，发现 2 小，再替换它们的地位，于是失去后果为 [1, 2, 3] 的数组。

当然，这个示例只是简略地阐明了一下替换排序的原理。但万变不离其宗，不论是冒泡还是快排，它们的基本原理和核心思想都是这样的，让两个数据比照后依据规定替换地位。这里其实从代码中咱们可能从一个中央很快地分辨出一段排序代码是否是替换排序，那就是他们会有一个对于两个元素进行数据交换的过程，而且往往在一般状况下会应用一个两头变量。这个咱们一会看代码就能够看到。

冒泡排序

冒泡排序，先从名字来了解一下，它的意思其实是让数据像汽水中的泡泡一样一个一个的浮上来。

间接上代码了来看看，代码其实非常简单。

function BubbleSort($numbers)
{$n = count($numbers);

    for ($i = 0; $i < $n - 1; $i++) { // 外层循环 n - 1
        for ($j = 0; $j < $n - $i - 1; $j++) { // 内层循环 n - 1 - i
            if ($numbers[$j] > $numbers[$j + 1]) { // 两两相比来替换
                $temp = $numbers[$j + 1];
                $numbers[$j + 1] = $numbers[$j];
                $numbers[$j] = $temp;
            }
        }
    }

    print_r($numbers);
}

BubbleSort($numbers);
// Array
// (//     [0] => 13
//     [1] => 27
//     [2] => 38
//     [3] => 49
//     [4] => 49
//     [5] => 65
//     [6] => 76
//     [7] => 97
// )

光看代码本人推演的话其实还是不太好了解，那么咱们就还是使出终极杀器，也就是图解步骤来看一下吧！

在代码中能够看到，咱们有两层循环。所以这个图片中咱们也是展现了 i 和 j 的两层循环状况。当然，限于篇幅，咱们只展现了第一次 i 循环外部的 j 循环状况，也就是 i = 0 时，外面的 j 循环执行的状况。

• i = 0 是，外部的 j < n – 1 – i，也就是外部的 j 要循环七次。咱们间接就看左边的 j 循环的步骤。
• 冒泡排序其实就是利用 j 和 j + 1 来比照两个相邻的元素。从图中咱们就能够看出，每一次 j++ 都是在对以后 j 和下一个 j + 1 的元素进行比拟。如果以后的这个 j 大于 j + 1 的话，就把它们替换地位。
• 当 j = 0 时，第 0 个地位的 49 是大于第 1 个地位的 38 的，于是 49 和 38 替换了地位。
• 当 j = 1 时，地位 1 的 49 和地位 2 的 65 相比，没有达成条件，于是不会变动。同理，j = 2 时也是比照的 65 和 97，同样不会产生替换。
• 当 j = 3 时，97 比 76 要大，于是产生了替换，97 替换到 j + 1 也就是下标 4 的地位。同时，97 也是整个序列中最大的数，于是前面会始终替换到这次的 j 循环完结。
• 最终的后果是 97 这个最大的数挪动到了数据的最初一位。也就是说，最大的数曾经放到了整个序列中的正确的地位上了。
• 接着内层循环完结，i++，开始第二次 i = 1 的外部 j 循环。这里须要留神的是，为什么咱们要用 j < n – 1 – i 呢？因为咱们后面曾经实现了一个最大数的排序，就是将 97 这个最大数放到了最初的地位上。所以在 i++ 的第二次循环时，咱们就要将第二大的数放在倒数第二的地位上。这时的 j 也不须要循环到最初一位了，只须要循环到倒数第二位就能够了。

从下面的分步解说中，咱们能够看到，外层的 i 每一次的循环其实就是通过内层的 j 循环来将一个最大的数按程序放到前面的地位上。就像汽水一直地向上冒泡一样，它就是传说中的冒泡排序算法概念的由来。

其实对于冒泡排序的算法，还有一个口决是很多同学都晓得的，也能够帮忙咱们记忆。

• 外层循环 N 减一
• 内层循环 N 减一减 I
• 两两相比小靠前（正序）

为什么小的靠前是正序呢？在代码中，咱们 if 条件判断是的 j > j+1，如果成立就替换它们，也就是让大的数据放到了前面，小的数据放到了后面，这样一轮过后，最大的数据放在了最初一位，也就是实现了一个最大数据的地位的确定。如果咱们将条件反过来，也就是 j < j+1 的话，就会让最大的数据放到最后面，也就是实现了倒序。是不是很神奇？小伙伴们能够试试哦，就扭转一下 if 条件的大于号就能够了哦。

冒泡的工夫复杂度其实很显著地就能看进去，O(N²)。属于效率个别但十分好了解的一种算法，而且它是一个稳固的排序算法。

疾速排序

冒泡的感觉咋样？不过冒泡有个问题，那就是它只能对相邻的两个数据进行比拟，所以 O(N²) 这个工夫复杂度根本也就不蕴含什么最好最坏的状况了，不管怎么它都得要达到这个 O(N²) 的程度。

那么有没有什么别的办法可能对冒泡进行优化呢？有大佬就创造出了优化冒泡的一种排序算法啦。那就是疾速排序算法。还记得在学习查找的时候咱们学习过的二分查找吗？绝对于线性查找来说，二分查找的效率是不是晋升了很多。但疾速排序的效率晋升可达不到那么高，毕竟排序还是比查找要简单些。而且它是在冒泡的根底上进行的改进，同样也应用了二分的思维，也就是分而治之的一种理念。让每次的比拟不再只是两个相邻的元素一个一个地比拟。所以它的均匀工夫复杂度能够晋升到 O(NlogN) 的级别。绝对于 O(N²) 来说，这个工夫复杂度其实也有了不小的飞跃哦。特地是数据量越大的状况下越显著。

同样咱们先来看看代码，而后再来看图剖析这个算法。

function QSort(&$arr, $start, $end)
{if ($start > $end) {return;}
    $key = $arr[$start];
    $left = $start;
    $right = $end;
    
    while ($left < $right) {
        // 左边下标确定
        while ($left < $right && $arr[$right] >= $key) {$right--;}
        // 右边下标确定
        while ($left < $right && $arr[$left] <= $key) {$left++;}
        if ($left < $right) { // 替换步骤
            $tmp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $tmp;
        }
    }

    $arr[$start] = $arr[$left];
    $arr[$left] = $key;
    // 递归左右两边持续
    QSort($arr, $start, $right - 1);
    QSort($arr, $right + 1, $end);
}

function QuickSort($numbers)
{QSort($numbers, 0, count($numbers) - 1);
    print_r($numbers);
}

QuickSort($numbers);
// Array
// (//     [0] => 13
//     [1] => 27
//     [2] => 38
//     [3] => 49
//     [4] => 49
//     [5] => 65
//     [6] => 76
//     [7] => 97
// )

有没有发现相熟的身影？没错，疾速排序应用到了递归。这个递归其实也蕴含着分治的思维，就像秦国对立六国一样，分而治之。咱们将某一个数据放到指定的地位之后再按左右分治的形式来持续其它的数据的排序，而不必让其它的数据再对整个序列进行残缺的判断，从而进步排序的效率。因而，快排的工夫复杂度绝对冒泡来说就好了很多。

同样地，它外表上是不停地递归，其实递归也是一种循环，咱们就可以看进去，它和冒泡一样其实是有着两层循环的概念的。这里咱们也是以第一次的外层循环为例子来分析它的内层循环都做了什么。

• 首先，咱们确定了一个关键字 key，这里咱们就间接指定第一个数据 49。而后指定左右两个指针，左指针 left 从 0 开始，右指针 right 从最左边的下标开始。
• 进入内层循环，条件是 left < right，也就是左右两个指针不能相遇！
• 开始指针挪动，先从左边开始，如果 right 指向的数据大于等于 key，right 就进行减减操作，否则，指针就停住。能够看到，咱们的指针停在了 27 这个数据的地位，也就是倒数第二个数据这里，第一个数据 49 和咱们的 key 值 49 是一样的，于是 right 就挪动到倒数第二个数据了，27 是小于 key 值的。
• 而后挪动 left 指针，挪动到符合条件的地位也就是值为 65 的这个下标，而后替换 left 和 right 的值。
• 持续后续的操作，直到 left 和 right 相遇了，这时退出循环，并在循环里面再次替换 key 和 left 地位的值。这时，第一个下标的 49 这个值就曾经放到了它所确定的地位。也就是说，这个值实现了排序。
• 接着，以这个实现排序的值为核心，切分左右两个序列，持续进入递归排序的过程，直到所有数据实现排序。

看出疾速排序和冒泡排序的区别了吧？快排的每趟排序都会确定一个关键字的具体位置，它的比拟除了第一次是每个数都和 key 两两比拟之外，其它都是采纳分治的思维来放大 n 的大小进行小范畴的排序的。而且每次的循环都会将数据按针对 key 值的大小进行左右排列，这也是二叉搜寻树的核心思想。这个内容咱们的系列文章中没有解说，大家能够自行查阅相干的材料学习。

小彩蛋：替换两个变量的值

明天学习的内容中都有一处外围的代码，就是最开始咱们说过的替换两个变量值的代码。

// 冒泡中
$temp = $numbers[$j + 1];
$numbers[$j + 1] = $numbers[$j];
$numbers[$j] = $temp;

// 快排中
$tmp = $arr[$left];
$arr[$left] = $arr[$right];
$arr[$right] = $tmp;

咱们都应用到了一个长期变量来进行替换。不过不少的面试题中常常会看到一种题目就是不应用第三个变量，也就是这个长期变量来替换两个变量的值。大家有没有踫到过呢？其实有几种计划都能够，咱们就来简略说两个。

$a = 1;
$b = 2;
$a += $b; // a = 3
$b = $a - $b; // b = 3 - 2 = 1 
$a = $a - $b; // a = 3 - 1 = 2
echo $a, PHP_EOL; // 2
echo $b, PHP_EOL; // 1

$a = "a";
$b = "b";
$a .= $b; // a = "ab"
$b = str_replace($b, "", $a); // b = str_replace("b","", "ab") = a
$a = str_replace($b, "", $a);// a = str_replace("a","", "ab") = b
echo $a, PHP_EOL; // b
echo $b, PHP_EOL; // a

对于数字来说，间接应用第一段的加减操作就能够实现两个变量的替换。而对于字符串来说，就能够应用 str_replace() 来实现。其实它们的思维都是一样的，先合并到一个变量上，而后利用减法或者替换来让某一个变量先变成另一个变量的值。而后再应用雷同的办法将另一个变量的值也转换胜利。当然，这只是最简略最根底的一种算法，利用 PHP 的一些函数和个性，咱们还能够更不便地实现这种性能。

$a = 1;
$b = 2;
list($a, $b) = [$b, $a];
echo $a, PHP_EOL; // 2
echo $b, PHP_EOL; // 1

list() 函数是将一个数组中的数据别离存入到指定的变量中，而在 PHP 中咱们也能够间接 [x, x] 这样来定义数组。所以不应用第三个长期变量来替换两个变量的性能咱们只用这一行代码就搞定了。list($a, $b) = [$b, $a]。这里不点赞可真对不起这道题咯！！

总结

替换排序的这两种算法相当于数据结构与算法这门课程的门面担当，凡是要讲算法中的排序的，必然会有它们两个的身影。毕竟太经典了，不过咱们可是先学了两个插入类的排序进行过了热身才来学习这两个经典算法的，置信大家进行比照之后就能更深刻地了解这些算法的神奇和不同。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/7. 排序 /source/7.2 替换排序：冒泡、快排.php

参考文档：

本文示例选自《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

各自媒体平台均可搜寻【硬核项目经理】