分解javascript冒泡排序算法

掌握算法，先理解原理

冒泡排序.gif

一趟冒泡

function bubbleSort(arr) {
     for (var j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                交换位置...分解见下
            }
        }
}

交换位置：

var temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp

交换图

很好理解，我们a,b 交换位置，我们先把a 移走，然后再把b 放进a，最后把 a 放到 b,实现交换

这样下来 ，一趟冒泡就是

function bubbleSort(arr) {
     for (var j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                 //交换位置
                 var temp = arr[j]
                 arr[j] = arr[j + 1]
                 arr[j + 1] = temp
            }
        }
}

从冒泡排序中可以发现，第一趟冒泡之后确定最大值，需要遍历的长度逐级递减
也可以这样理解,每一趟冒泡，会确定数组中一个值的位置，那么需要遍历的长度减 1

function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
       //外部循环
        for (var j = 0; j < arr.length - 1; j++) {
        //内部循环
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }

    }
    return arr;
}

总结：
内部循环是每一趟冒泡返回的交换结果，
外部循环是程序需要跑多少趟能排好序

进一步优化程序

我们有这样一种情况
就是当数组已经是排好序(正序)的时候，例如[1,2,3,4,5,6]
这种全程无交换的状态我们怎么优化程序？

var array = [1,2,3];
var num = 0
function bubbleSort(arr) {
   for (var i = 0; i < arr.length - 1; i++) {  //最大需要跑的趟数
       var isSort = true; //默认是排好序（正）的
       for (var j = 0; j < arr.length - 1; j++) {
           if (arr[j] > arr[j + 1]) {
               var temp = arr[j]
               arr[j] = arr[j + 1]
               arr[j + 1] = temp
               isSort = false
           }
       }
       if (isSort) break;  //如果是排序的，跳出程序
       num++

   }

   return arr;
}

bubbleSort(array)
console.log(array, '比较' + num + '次数')    //打印 [ 1, 2, 3 ] '比较0次数'

声明一个flag标识，如果有交换，则继续循环，如果全程无交换，直接跳出程序，这时候程序只需要执行一次，也就是空间复杂度最优状态
T = O（N）

反之，如果数组是逆序，空间复杂度最坏状态

T = O（N^2）