【排序】交换排序之冒泡排序

发表于   |   分类于 算法   |   暂无评论

    自己之前对于排序的使用一直都是来自于对sort,ksort等排序函数的基础上，但是对具体的算法原理没有具体考虑过。闲下来，就思考下这些算法的实现。那么本篇文章以及未来的一系列排序文章，将总结排序在php中的原理以及实现：

冒泡排序

冒泡排序算是排序中最基本、也最容易理解的排序算法了。以下引自百度百科：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

先贴一下冒泡排序的代码，再逐一分析其中的奥妙（这里以从小到大排序为例）：

冒泡代码

$numbers = [66, 64, 65, 54, 100, 89, 11, 2];
$len = count($numbers);
for ($i = 0; $i < $len; $i++) {
    for ($j = 0; $j < $len - $i - 1; $j++) {
        if ($numbers[$j] > $numbers[$j + 1]) {
            $temp = $numbers[$j];
            $numbers[$j] = $numbers[$j + 1];
            $numbers[$j + 1] = $temp;
        }
    }
}

原理分析

短短数行代码就可以实现冒泡排序，但其中的原理并不简单，简单归纳为一下几点：

  1. 第一次拿下标为0和下标为1的元素进行比较

  2. 每次拿相邻的两个元素进行比较，根据排序规则，进行顺序调换；比如从小到大排序，则每次在比较相邻两个元素大小的时候，把元素小的那一方提到原先元素大的那一方的下标上，把元素大的那一方提到原先元素小的那一方下标上；

  3. 两两一对，每一对都进行比较

  4. 最外围的for循环，每一次循环完毕都能得到当前循环组里的最大值，在数组末尾依次排列

代码分解

我们可以先看一下内层for循环，第一次循环完毕的结果：

// 原先的数组：
Array ( [0] => 66 [1] => 64 [2] => 65 [3] => 54 [4] => 100 [5] => 89 [6] => 11 [7] => 2 ) 

// 第二层for循环第一次循环，每次的结果
Array ( [0] => 64 [1] => 66 [2] => 65 [3] => 54 [4] => 100 [5] => 89 [6] => 11 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 66 [3] => 54 [4] => 100 [5] => 89 [6] => 11 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 54 [3] => 66 [4] => 100 [5] => 89 [6] => 11 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 54 [3] => 66 [4] => 100 [5] => 89 [6] => 11 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 54 [3] => 66 [4] => 89 [5] => 100 [6] => 11 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 54 [3] => 66 [4] => 89 [5] => 11 [6] => 100 [7] => 2 ) 
Array ( [0] => 64 [1] => 65 [2] => 54 [3] => 66 [4] => 89 [5] => 11 [6] => 2 [7] => 100 )

从上面的执行结果中我们可以看到，第一行结果相比较最初的数组而言，两两比较，元素小的那一个已经提到了前面，这里验证了我们【原理分析】里第一点和第二点的描述；而且我们也得到了最大值，在数组的末尾。

第一层循环结束后，我们仍然看到数组的排序不是从小到大的顺序，所以要进行第二次元素排序；

由于每次内层for循环完毕后已经确定了最大值，所以在外围for循环第一次之后每次的排序后，都不需要再对确定好的最大值进行比较，所以有了内层循环中$j < $len - $i - 1这段代码，来看一下外层循环每次循环之后的结果：

外层循环每次循环完毕排序结果

结果我们可以验证内层循环，每次循环完毕都能确定最大值的说法；

if ($numbers[$j] > $numbers[$j + 1]) {
    $temp = $numbers[$j];
    $numbers[$j] = $numbers[$j + 1];
    $numbers[$j + 1] = $temp;
}

这段代码块起到交换两个元素的作用，如果元素1大于元素2，那么用一个临时变量把其中一个值存储在临时变量中，再进行下标元素的替换工作；

封装

下面代码块封装了冒泡排序正序、倒序的实现；

/**
 * 冒泡排序（asc正序列 desc倒序）
 * @param  array  $arr      排序数组
 * @param  string $sortType 排序类型
 * @return array            排序结果
 */
function bubbleSort($arr, $sortType = 'asc')
{
    $intLength = count($arr);
    for ($i = 0; $i < $intLength; $i++) {
        for ($j = 0; $j < $intLength - $i - 1; $j++) {
            // 正序排序
            if ($sortType == 'asc') {
                // 交换元素位置
                if ($arr[$j] > $arr[$j + 1]) {
                    $temp        = $arr[$j];
                    $arr[$j]     = $arr[$j + 1];
                    $arr[$j + 1] = $temp;
                }
            // 倒序排序
            } else {
                // 交换元素位置
                if ($arr[$j] < $arr[$j + 1]) {
                    $temp        = $arr[$j];
                    $arr[$j]     = $arr[$j + 1];
                    $arr[$j + 1] = $temp;
                }
            }
        }
    }

    return $arr;
}
$arrTmp = [66, 64, 65, 54, 100, 89, 11, 2];
p(bubbleSort($arrTmp));
p(bubbleSort($arrTmp, 'desc'));

总结

冒泡排序是排序算法中的基本，之前自己在学习C语言的时候，有幸接触到算法的相关知识。觉得算法乃是一门博大精深的学问，后面几章也会连续做排序算法的讲解；下章将介绍冒泡排序的兄弟——【快速排序】。
完。
添加新评论