【PHP数据结构】交换排序：冒泡、快速排序

上一篇我们学习了插入类相关的两种排序。不过，和交流班那种比起来，他们还真的只是小弟而已。甚至可以说，在所有的排序算法中，最著名的两种排序就是今天要介绍的交换排序。不管是冒泡排序还是快速排序，都是面试中常见的排序算法。它们有多常见？每当你学习数据结构和算法的时候，即使你根本没有学过，你也会或多或少听说过这两种排序算法。而一些大中型公司直接在面试题中表示不使用这两种算法来实现一些排序题。为什么是这样？当然，也是因为这两个算法太出名了，很多人都能手写出来。当然，不管你面试的公司有什么要求，只要是有志于编程开发??行业发展的同学，冒泡和快排肯定会是面试中绕不开的一道坎。今天就来好好了解一下这两种排序算法。但首先，有必要了解这个“交换”指的是什么。上一篇文章中的插入排序指的是直接将数据插入到指定位置。exchange的意思就是让两个位置的数据经过比较后可以直接交换。比如我们有一个数组[3,1,2]，需要按照[1,2,3]的形式排列。那么我们可以先比较3和1，发现1比较小，所以交换3和1的位置，结果就是[1,3,2]。然后比较3和2，发现2小，交换位置，结果就是[1,2,3]的数组。当然，这个例子只是简单说明交换排序的原理。但一切都保持不变。无论是冒泡还是快速排序，它们的基本原理和核心思想都是一样的。对比两个数据后，按规则交换位置。其实从代码中我们可以快速判断出一段排序代码是不是交换排序，也就是它们对于两个元素会有一个数据交换的过程，一般情况下往往会用到一个中间变量。一会儿我们看代码就可以看出这一点。冒泡排序冒泡排序，首先从名字上理解，它的意思就是让数据像苏打水中的气泡一样，一个一个的往上浮。直接上代码看看，代码其实很简单。函数BubbleSort($numbers){$n=count($numbers);for($i=0;$i<$n-1;$i++){//外循环n-1for($j=0;$j<$n-$i-1;$j++){//内循环n-1-iif($numbers[$j]>$numbers[$j+1]){//两两比较交换$temp=$numbers[$j+1];$数字[$j+1]=$数字[$j]；$numbers[$j]=$temp;}}}print_r($numbers);}BubbleSort($numbers);//数组//(//[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是，内部jj+1。如果是真的，我们就交换一下，就是让大数据放在后面，小数据放在前面。本轮结束后，将最大的数据放入最后一位，完成对一个最大数据位置的确定。如果我们把条件倒过来，即j$end){return;}$key=$arr[$start];$左=$开始；$右=$结束；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);}functionQuickSort($numbers){QSort($numbers,0,count($numbers)-1);print_r($numbers);}QuickSort($numbers);//数组//(//[0]=>13//[1]=>27//[2]=>38//[3]=>49//[4]=>49//[5]=>65//[6]=>76//[7]=>97//)找到熟悉的身影了吗？没错，quicksort使用递归。这个递归其实包含了分而治之的思想，就像秦统一六国一样，分而治之。我们将某条数据放到指定位置后，继续按照左右分治的方式对其他数据进行排序，不让其他数据对整个序列做完整判断，从而提高排序效率。因此，快速排序的时间复杂度要比冒泡好很多。同样，表面上是不断递归，其实递归也是一种循环。我们可以看到它其实和冒泡一样有两层循环的概念。这里我们也以第一个外层循环为例，分析一下它的内层循环做了什么。首先，我们确定了一个关键字key，这里我们直接指定第一个数据49。然后指定左右两个指针，左指针left从0开始，右指针right从最右边的下标开始。进入内层循环，条件为left