<?php

/**

 * 冒泡排序

 *

 * -------------------------------------------------------------

 * 思路分析：就是像冒泡一样，每次从数组当中 冒一个最大的数出来。 

 * -------------------------------------------------------------

 * 你可以这样理解：（从小到大排序）存在10个不同大小的气泡，

 * 由底至上的把较少的气泡逐步地向上升，这样经过遍历一次后最小的气泡就会被上升到顶（下标为0）

 * 然后再从底至上地这样升，循环直至十个气泡大小有序。

 * 在冒泡排序中，最重要的思想是两两比较，将两者较少的升上去

 *

 */

/**

 * BubbleSort

 *

 * @param array $container

 * @return array

 */

// function BubbleSort(array $container)

// {

//     $count = count($container);

//     for ($j = 1; $j < $count; $j++) {

//         for ($i = 0; $i < $count - $j; $i++) {

//             if ($container[$i] > $container[$i + 1]) {

//                 $temp = $container[$i];

//                 $container[$i] = $container[$i + 1];

//                 $container[$i + 1] = $temp;

//             }

//         }

//         echo 'good';

//     }

//     return $container;

// }

// print_r(BubbleSort([4, 21, 41, 2, 53, 1, 213, 31, 21, 423]));

//  优化一：

// 假设我们现在排序arr=[1,2,3,4,5,6,7,8,10,9]这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。

// function BubbleSort(array $container)

// {

//     $count = count($container);

//     for ($j = 1; $j < $count; $j++) {  //排序的趟数

//         $flag = false;

//         for ($i = 0; $i < $count - $j; $i++) {  //比较的次数

//             if ($container[$i] > $container[$i + 1]) {

//                 $temp = $container[$i];

//                 $container[$i] = $container[$i + 1];

//                 $container[$i + 1] = $temp;

//                 $flag = true; //交换元素的时候标记为true

//             }

//         }

//         if($flag == false){ //没有元素交换的话，则为有序

//             return $container;

//         }

//         echo 'good'; //用于查看排序多少趟

//     }

//     return $container;

// }

// print_r(BubbleSort([1,2,3,4,5,6,7,8,10,9]));

//优化二：[1,2,5,7,4,3,6,8,9,10]

//优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

// function BubbleSort(array $container)

// {

//     $count = count($container);

//     for ($j = 1; $j < $count; $j++) {  //排序的趟数

//         $flag = false;

//         $finalkey = 0;

//         $comparecount = $count - $j;

//         for ($i = 0; $i < $comparecount; $i++) {  //比较的次数

//             if ($container[$i] > $container[$i + 1]) {

//                 $temp = $container[$i];

//                 $container[$i] = $container[$i + 1];

//                 $container[$i + 1] = $temp;

//                 $flag = true; //交换元素的时候标记为true

//                 $finalkey = $i; //记录最后交换的位置

//             }

//         }

//         if($flag == false){ //没有元素交换的话，则为有序

//             return $container;

//         }

//         $comparecount = $finalkey; //下一次比较到该记录位置即可

//         echo 'good';

//     }

//     return $container;

// }

// print_r(BubbleSort([1,2,5,7,4,3,6,8,9,10])); 1,2,5,7,9,8,4,3,6,10,11,12

// 优化三：(最优化方案)

// 优化二的效率有很大的提升，还有一种优化方法可以继续提高效率。大致思想就是一次排序可以确定两个值，正向扫描找到最大值交换到最后，反向扫描找到最小值交换到最前面。例如：排序数据1,2,3,4,5,6,7,0

// function BubbleSort(array $container)

// {

//     $count = count($container);//数组的长度

//     for ($j = 1; $j < $count; $j++) {  //排序的趟数

//         $flag = false; //交换元素的时候标记为true，没有交换为false

//         $finalkey = 0;//标记最后交换的位置，下次循环也只循环到该位置

//         $comparecount = $count - $j;

//         //正向寻找最大值

//         for ($i = $n; $i < $comparecount; $i++) {  //比较的次数

//             if ($container[$i] > $container[$i + 1]) {

//                 $temp = $container[$i];

//                 $container[$i] = $container[$i + 1];

//                 $container[$i + 1] = $temp;

//                 $flag = true; //交换元素的时候标记为true

//                 $finalkey = $i; //记录最后交换的位置

//             }

//         }

//         if($flag == false){ //没有元素交换的话，则为有序

//             return $container;

//         }

//         $comparecount = $finalkey; //下一次比较到该记录位置即可

//         //反向寻找最小值

//         for($i = $comparecount;$i>0;$i--){

//             if($container[$i]>$container[$i+1]){

//                 $tmp = $container[$i+1];

//                 $container[$i+1] = $container[$i];

//                 $container[$i] = $tmp;

//                 $flag = true;

//             }

//         }

//         if($flag == false){ //没有元素交换的话，则为有序,直接结束

//             return $container;

//         }

//         echo 'good';

//     }

//     return $container;

// }

// print_r(BubbleSort([1,2,3,4,5,6,7,0])); //这个数组遍历两趟

//[1,2,5,7,9,8,4,3,6,10,11,12]  //这个遍历三趟，5,7,9,8,4,3,6   9，3一趟  8，4一趟  7，5一趟  6中间不用  
//有不好的地方欢迎指点