排序算法学习之路——冒泡排序

  • Z时代
  • 2024-01-10
  • 分类：综合

冒泡排序也是一种简单直观的排序算法。其思想是：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

下面我们通过一个简单的图例来了解一下这个冒泡的过程

起始位置为0，依次比较相邻的两个元素。如果前面的元素大于后面的元素，则进行交换。

我们可以看出，待排序序列有多少个元素，就需要几趟冒泡。但是在实际过程中，我们可以根据实际情况减少其冒泡的趟数。

就拿上例来说，我们看在第四趟冒泡完成以后就已经有序了。第五趟和第六趟冒泡过程并没有产生元素的交换。所以说我们可以判断，在一趟冒泡中如果没有产生元素的交换，我们就终止冒泡的整个过程。这样最后得到的序列同样是有序的。

反应在程序中就是在每一趟冒泡的开始设置一个标志位，默认为false。当有交换产生的时候将该标志位设为true。在该趟冒泡过程结束以后，我们根据此标志位来判断是否有交换的产生。如果没有交换产生的话，我们就直接结束整个冒泡过程。否则继续下一趟冒泡。

根据上图，我们来看一下实现冒泡排序的文字的步骤

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

最后我们要将文字步骤转换成代码实现

/**
 * 交换函数
 */
functionswap(&$arr,$a,$b){
$t = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $t;
}
functionBubbleSort(&$arr){
$end = count($arr)-1;
while($end>0){
for($i=0;$i<$end;$i++){
if($arr[$i]>$arr[$i+1]){
                swap($arr,$i,$i+1);
            }
        }
$end--;
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
BubbleSort($arr);
print_r($arr);

上述代码是将所有的冒泡过程都走了一遍，下面我们只需要将BubbleSort函数进行简单的修改就可以实现上述我们说的标志位来判断是否有交换的产生。

functionBubbleSort(&$arr){
$end = count($arr)-1;
while($end>0){
$flag = false;  //每次冒泡前 初始化标志位为false
for($i=0;$i<$end;$i++){
if($arr[$i]>$arr[$i+1]){
                swap($arr,$i,$i+1);
$flag = true;  //有交换产生 将标志位置为true
            }
        }
if(!$flag) break;  //如果没有交换产生 则直接跳出循环
$end--;
    }
}

其实带标志位的和不带标志位的程序在数据量很小的时候并没有明显的差别，所用时间应该没有什么差别。但是在数据量很大的时候其差别就会变得很明显。但是话又说回来，冒泡排序并不是最好的排序算法，其效率较其他的排序算法低，时间复杂度为O(n²)。所以说在实际情况中如果数据量很大的话也不一定我们会选择冒泡排序来实现排序。

但是我个人觉得冒泡排序和选择排序可以说是其他排序的基础，所以我们有必要去了解冒泡排序。

希望本文对大家有所帮助。

本文转载自：迹忆客（https://www.jiyik.com）

以上是 排序算法学习之路——冒泡排序 的全部内容， 来源链接： utcz.com/z/290052.html

回到顶部