当然，不管你口试的公司有什么哀求，只假如有志在编程开拓这个行业里发展的同学，冒泡和快排肯定会是口试中绕不开的一个坎。我们本日就来好好地学习一下这两个排序算法。不过首先还是要搞明白这个“交流”指的是什么意思。
上篇文章中的插入排序，指的是直接将数据插入到指定的位置。而交流的意思，则是让两个位置的数据在进行比对后直接交流。比如我们有 [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(N2)。属于效率一样平常但非常好理解的一种算法，而且它是一个稳定的排序算法。
快速排序冒泡的觉得咋样？不过冒泡有个问题，那便是它只能对相邻的两个数据进行比较，以是 O(N2) 这个韶光繁芜度基本也就不包含什么最好最坏的情形了，不管怎么它都得要达到这个 O(N2) 的水平。
那么有没有什么别的方法能够对冒泡进行优化呢？有大佬就发明出了优化冒泡的一种排序算法啦。那便是快速排序算法。还记得在学习查找的时候我们学习过的二分查找吗？相对付线性查找来说，二分查找的效率是不是提升了很多。但快速排序的效率提升可达不到那么高，毕竟排序还是比查找要繁芜些。而且它是在冒泡的根本上进行的改良，同样也利用了二分的思想，也便是分而治之的一种理念。让每次的比较不再只是两个相邻的元素一个一个地比较。以是它的均匀韶光繁芜度可以提升到 O(NlogN) 的级别。相对付 O(N2) 来说，这个韶光繁芜度实在也有了不小的飞跃哦。特殊是数据量越大的情形下越明显。
同样我们先来看看代码，然后再来看图剖析这个算法。
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 = 2echo $a, PHP_EOL; // 2echo $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") = becho $a, PHP_EOL; // becho $b, PHP_EOL; // a
对付数字来说，直策应用第一段的加减操作就可以完成两个变量的交流。而对付字符串来说，就可以利用 str_replace() 来实现。实在它们的思想都是一样的，先合并到一个变量上，然后利用减法或者更换来让某一个变量先变成另一个变量的值。然后再利用相同的方法将另一个变量的值也转换成功。当然，这只是最大略最根本的一种算法，利用 PHP 的一些函数和特性，我们还可以更方便地实现这种功能。
$a = 1;$b = 2;list($a, $b) = [$b, $a];echo $a, PHP_EOL; // 2echo $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
参考文档：
本文示例选自 《数据构造》第二版，严蔚敏
《数据构造》第二版，陈越
