冒泡排序

原理: 1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。 2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大(小)的数。 3、针对所有的元素重复以上的步骤,除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较 分析: 最好的时间复杂度为O(n),最坏的时间复杂度为O(n2) 稳定性: 属于稳定性排序

示例:

<?php
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
for($i = 0; $i < $num; $i++) {
    for($j = 0; $j < $num - $i - 1; $j++){         $total++;         if($arr[$j] > $arr[$j+1]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j+1];
            $arr[$j+1]  = $temp;
        }
    }
}
echo $total;//66次循环
print_r($arr);

优化:
如果内层循环没有进行交互则表示已经排序完成

$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$total = 0;
$num = count($arr);
$break = false;
for($i = 0; $i < $num; $i++) {
    $break = true;
    for($j = 0; $j < $num - $i - 1; $j++){         $total++;         if($arr[$j] > $arr[$j+1]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j+1];
            $arr[$j+1]  = $temp;
            $break = false;
        }
    }
    if($break) {
        break;
    }
}
echo $total;//45次循环
print_r($arr);
//优化第二步    
//缩减内层循环排序区间,如果0到i的位置是有序,那么上次循环区间是i到n
//交换的位置在i到n之间的pos位置
//其中可以知道i到pos的位置是有序的,那么下次循环就可以从post到n
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$break = false;
$lastSwapPos  = $lastSwap = 0;
for($i = 0; $i < $num - 1; $i++) {     $lastSwap = $lastSwapPos;     for($j = $num - 1; $j > $lastSwap; $j--){
        $total++;
        if($arr[$j - 1] > $arr[$j]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j - 1];
            $arr[$j - 1]  = $temp;
            $lastSwapPos = $j;
        }
    }
    if($lastSwap == $lastSwapPos) {
        break;
    }
}
echo $total;//39次循环
print_r($arr);
//双向冒泡(鸡尾酒排序)
/*
原理
数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。
然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序
*/
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$left = 0;
$right = $num - 1;
while ($left < $right) {
    $l = $left + 1;
    $r = $right - 1;
    for($i = $left; $i < $right; $i++) {
        $total++;
        if($arr[$i] > $arr[$i+1]) {
            $temp1 = $arr[$i];
            $arr[$i] = $arr[$i+1];
            $arr[$i+1] = $temp1;
            $r = $i;
        }
    }
    $right = $r;
    for($j = $right;$j > $left; $j--) {
        $total++;
        if($arr[$j] < $arr[$j - 1]) {
            $temp2 = $arr[$j-1];
            $arr[$j - 1] = $arr[$j];
            $arr[$j] = $temp2;
            $l = $j;
        }
    }
    $left = $l;
    
}
echo $total;//30次循环
print_r($arr);

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快速排序

    思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排...

    苦咖啡
  • 蛇形矩阵

    <?php /* * 蛇形矩阵一 */ $n = 5; //填充数组,array_fill第一个参数是起始下标,第二个是总个数,第三个是元素 $ar...

    苦咖啡
  • 奇偶排序

    原理 奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对,a[j]和a[j+1],j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序...

    苦咖啡
  • js中数组常用逻辑算法(从大到小,从小到大排序,去重等问题)

    honey缘木鱼
  • 常用算法比较,js实现

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • LeetCode 5429. 数组中的 k 个最强值

    设 m 为数组的中位数,只要满足下述两个前提之一,就可以判定 arr[i] 的值比 arr[j] 的值更强:

    freesan44
  • 前端十大经典排序算法

    冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是...

    enoyo
  • [-算法篇-] 排序

    张风捷特烈
  • 排序算法之选择排序-java版

    选择排序类似于冒泡排序,均属于内排,也可以看做是对冒泡排序的优化。因为冒泡排序是比较相邻的两个值,然后直接交换。而选择排序是找到一个最大值或者最小值之后,再进行...

    shengjk1
  • JavaScript数组排序总结

    将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍...

    用户4831957

扫码关注云+社区

领取腾讯云代金券