分解javascript冒泡排序算法分解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

文章图片
交换图 【分解javascript冒泡排序算法】很好理解，我们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）