什么是冒泡排序？

    冒泡排序的思想：把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于右侧相邻元素时，位置不变。

  1 <?php
  2 
  3 class Sort
  4 {
  5     /**
  6      * 冒泡排序的第一种写法
  7      * @param array $arr
  8      * @return array
  9      */
 10     public function bubbleSort1(array $arr): array
 11     {
 12         $length = count($arr);
 13         for ($i = 0; $i < $length - 1; $i++) {
 14             for ($j = 0; $j < $length - $i - 1; $j++) {
 15                 if ($arr[$j] > $arr[$j + 1]) {
 16                     $temp = $arr[$j];
 17                     $arr[$j] = $arr[$j + 1];
 18                     $arr[$j + 1] = $temp;
 19                 }
 20             }
 21         }
 22         return $arr;
 23     }
 24 
 25 
 26     /**
 27      * 冒泡排序的第二种写法
 28      * @param array $arr
 29      * @return array
 30      */
 31     public function bubbleSort2(array $arr): array
 32     {
 33         $length = count($arr);
 34 
 35         for ($i = 0; $i < $length - 1; $i++) {
 36             // 是否排序标识：如果没有交换，则列表已经完成排序
 37             $isSorted = false;
 38             for ($j = 0; $j < $length - $i - 1; $j++) {
 39                 if ($arr[$j] > $arr[$j + 1]) {
 40                     $temp = $arr[$j];
 41                     $arr[$j] = $arr[$j + 1];
 42                     $arr[$j + 1] = $temp;
 43                     $isSorted = true;
 44                 }
 45             }
 46 
 47             if (!$isSorted) {
 48                 break;
 49             }
 50         }
 51         return $arr;
 52     }
 53 
 54     /**
 55      * 冒泡排序的第三种写法
 56      * @param array $arr
 57      * @return array
 58      */
 59     public function bubbleSort3(array $arr): array
 60     {
 61         $length = count($arr);
 62 
 63         // 记录每一轮最后一次交换的下标
 64         $swapOffset = 0;
 65 
 66         for ($i = 0; $i < $length - 1; $i++) {
 67             // 是否排序标识：如果没有交换，则列表已经完成排序
 68             $isSorted = false;
 69 
 70             // 记录的交换下标之后的元素已经完成排序，不用再次排序
 71             $swapOffset = $swapOffset ?: ($length - $i - 1);
 72             for ($j = 0; $j < $swapOffset; $j++) {
 73                 if ($arr[$j] > $arr[$j + 1]) {
 74                     $temp = $arr[$j];
 75                     $arr[$j] = $arr[$j + 1];
 76                     $arr[$j + 1] = $temp;
 77 
 78                     // 记录每一轮最后一次交换的下标
 79                     $swapOffset = $j;
 80                     $isSorted = true;
 81                 }
 82             }
 83 
 84             if (!$isSorted) {
 85                 break;
 86             }
 87 
 88             if (!$swapOffset) {
 89                 break;
 90             }
 91         }
 92         return $arr;
 93     }
 94 }
 95 
 96 /**
 97  * 分析：
 98  * 1）n个元素，则外层两两比较 n-1 次
 99  * 2）冒泡排序最重要的一个方面是，对于外循环中的每次迭代，都会有至少一次交换。如果没有交换，则列表已经排序
100  * 时间复杂度：n-1+ n-2+.....+2+1= n *（n-1）/2= O(n2)
101  */
102 
103 $arr = [1, 10, 2, 11, 12];
104 $sort = new Sort();
105 //$res = $sort->bubbleSort1($arr);
106 //$res = $sort->bubbleSort2($arr);
107 $res = $sort->bubbleSort3($arr);
108 var_dump($res);