第 54 题：冒泡排序如何实现，时间复杂度是多少， 还可以如何改进？

Question

时间复杂度： n^2

// 生成从l到r的数量为n的随机数组
function randomArr (n, l, r) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        let _random = Math.round(l + Math.random() * (r - l));
        arr.push(_random)
    } 
    return arr;
}
function buddleSort (arr) {
    let len = arr.length;
    for (let i = len;  i >= 2;  i-- ) {
        for (let j = 0;  j < i - 1;  j++) {
             if (arr[j] > arr[j+1]) {
                  [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
             }
        }
    }
    return arr;
}
console.log(buddleSort(randomArr(10, 5, 100)));

Answer 1

长知识了~

Answer 2

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

@guokangf 这个改良算法能解释一下吗？

根据上述代码，我们每一轮冒泡需要的结果就是把最大的数通过冒泡放到最后，然后缩小下一轮需要冒泡的数组的范围（未优化的方案中数组范围只缩小了一位），但是实际上我们每一轮冒泡后可能会出现后面的几个数都有序的情况，这个时候我们完全可以再缩小一点下一次需要冒泡的数组的范围（不然下一轮冒泡到最后发现最大的数本来就在最后，此次冒泡就是多余的）。那怎么确定这个i值呢？

举个栗子：
[a[0],...,a[j],a[j+1],...,a[i]]
如果某一次冒泡比较中a[j]>a[j+1]
交换两值，此时a[j+1]大于a[0]到a[j]的任何值（a[0]到a[j]还是无序的）
如果再接下来的冒泡中满足a[j+1]到a[i]有序，即不做任何交换操作（a[j]和a[j+1]是最后一次交换操作）
那我们下一轮只需要对a[0]到a[j]的无序数组进行冒泡排序，j就是下一轮循环的i值

Answer 3

@wwwxy80s 我这边的冒泡排序的改良思路是，如果某一次遍历，没有进入过if条件，则表示已经是排好的顺序了，跳出循环

Answer 4

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {  // 此处还需要减去i 每一次排序都会排序好i 个数据
      let temp = '';
      if (arr[j] > arr[j + 1]) {
        temp = arr[j]
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
bubbleSort([1,4,3,5,2,10,8,9])

function bubbleSort2(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let finish = true;
    let pos = 0;
    let len = arr.length - 1 - i;
    for(let j = 0; j < len; j++) {
      let temp = '';
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        finish = false; // 是否还有交换 ，没有互换则代表排序排好了
        pos = j // 最后一次交换的位置，之后的数据不需要再遍历
      }
    }
    len = pos;
    if (finish) {
      break;
    }
  }
  return arr;
}
bubbleSort2([1,4,3,5,2,10,8,9])

Answer 5

时间复杂度： O(n^2)

一般的冒泡：

function bubbleSort1(arr) {
	for (let i = 0; i < arr.length - 1; i++) {
		for (let j = 0; j < arr.length - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
			}
		}
	}
}

这个存在的问题是，每次循环一次，后面就会多一段有序的数组，然而每次还是遍历了，是多余了

优化一下这个问题

function bubbleSort2(arr) {
	// i是j需要遍历的次数，并不用i来遍历内容。
	// 这样，每次会把上一次排过的数组滤过，只排列前面还没有排列的部分
	// 每一次j就可以少遍历一次
	for (let i = arr.length-1; i >= 0; i--) {	
		for (let j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
			}
		}
	}
}

对于这个方案，还可以改进
如果剩下的还没有排序的部分，本身就是有序的，也可以让遍历跳过，就又可以省下不少时间
例如这种： let a = [1, 2, 3, 4, 5, 6, 3, 11, 12, 9, 5, 8, 7, 23, 6, 8, 9];

function bubbleSort3(arr) {
	var swapedFlag;
	for (var i = arr.length - 1; i >= 0; i--) {
		swapedFlag = false;
		for (var j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				swapedFlag = true;
				[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
			}
		}
		// 如果j遍历，从头到尾都没有把swapedFlag置为true，就证明剩下的一段数组，本来就是按顺序的，就不用再遍历了
		if (!swapedFlag) {
			break;
		}
	}
}

Answer 6

普通：冒泡排序
改良：鸡尾酒排序（就是先向上冒个泡，再向下冒个泡，如此重复）

Answer 7

```js
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

@guokangf 这个改良算法能解释一下吗？

每次最大值放到最右后，会将本轮最后一个操作的位置作为下一轮的终点，可以减少不必要的一些冒泡

标准实现中的 j < arr.length - i - 1; 循环条件不已经达到这个目的了吗？？

Answer 8

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

这个改进版 是不是 每次取最后一次调换位置的下标 作为 下一次循环的长度？？？？？

Answer 9

```js
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

@guokangf 这个改良算法能解释一下吗？
每次最大值放到最右后，会将本轮最后一个操作的位置作为下一轮的终点，可以减少不必要的一些冒泡

标准实现中的 j < arr.length - i - 1; 循环条件不已经达到这个目的了吗？？

不一样的 改良版的可以跳跃的 j < arr.length - i - 1 标准的是 每次都是一次递减的，不管是不是存在部分冒泡好的

Answer 10

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}
bubbleSort([3, 1, 15, 7, 5])

Answer 11

另一种写法：

function bubbleSortV2(arr) {
  if (!arr || !arr.length) {
    return [];
  }

  for (let r = arr.length-1; r > 0; ) {
    let tempIndex = 0;
    for (let l = 0; l < r; l++) {
      if (arr[l] > arr[l + 1]) {
        // 缩小需要冒泡的范围
        tempIndex = l;
        [arr[l], arr[l + 1]] = [arr[l + 1], arr[l]];
      }
    }
    // 更新冒泡范围
    r = tempIndex;
  }
}

Answer 12

冒泡排序概念：依次比较相邻的两个元素，如果顺序倒置则交换相邻元素。

Answer 13

for (let i = 0;i < ary.length;i++) {
       for (let j = 0;j < ary.length - i - 1;j++) {
            if (ary[j] > ary[j + 1]) [ary[j], ary[j + 1]] = [ary[j + 1], ary[j]];
       }
 }

Answer 14

var bubbleSort = function(arr) {
		var temp = null;
		for (var i=arr.length-1;i>=0;i--){
			var flag = true; // 循环开始时设置一个flag为true，若在一个循环中没有发生交换，则数组已经有序，可以直接退出
			for (var j=0;j<i;j++) {
				if(arr[j]>arr[j+1]){
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
					flag = false;
				}
			}
			if(flag) break;
		}
		return arr;
	}

Answer 15

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

@guokangf 这个改良算法能解释一下吗？

每次最大值放到最右后，会将本轮最后一个操作的位置作为下一轮的终点，可以减少不必要的一些冒泡

Answer 16

arr = [5,4,22,33,11,66]
arr.sort(function(a,b){
return a-b })
console.log(arr)

Answer 17

function random(n,x,y){
  let arr = [];
  for(let i = 0; i < n; i++){
    let num = (x + Math.random() * (y - x)) | 0;
    arr.push(num);
  }
  return arr;
};
function sort(arr){
  let leng = arr.length;
  for(let i = 0; i < leng; i++){
    for(let j = 0; j < leng - i - 1; j++){
      if(arr[j] > arr[j + 1]){
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp; 
      }
    }
  }
  return arr;
}
console.log(sort(random(5,5,50)));

练个手

Answer 18

// 冒泡排序
const bubbleSort = (array) => {
  const newArray = [...array]
  const len = newArray.length
  if (len <= 1) return 
  let isChange = false
  for(let i = 0; i < len; i++) {

    for (let j = i; j < len - i - 1; j++) {
      if (newArray[j + 1] < newArray[j]) {
        let temp = newArray[j + 1]
        newArray[j + 1] = newArray[j]
        newArray[j] = temp
        isChange = true
      }
    }

    if (!isChange) break

  }
  return newArray
}

时间复杂度 O(n^2)

Answer 19

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

@guokangf 这个改良算法能解释一下吗？

Answer 20

时间复杂度： n^2

// 生成从l到r的数量为n的随机数组
function randomArr (n, l, r) {
    let arr = [];
    for (let i = 0; i < n; i++) {
        let _random = Math.round(l + Math.random() * (r - l));
        arr.push(_random)
    } 
    return arr;
}
function buddleSort (arr) {
    let len = arr.length;
    for (let i = len;  i >= 2;  i-- ) {
        for (let j = 0;  j < i - 1;  j++) {
             if (arr[j] > arr[j+1]) {
                  [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
             }
        }
    }
    return arr;
}
console.log(buddleSort(randomArr(10, 5, 100)));

bubble

Answer 21

function sort(values) {
  var origValues = values.slice();
  do {
    var swapped = false;
    for(var i = 0; i < origValues.length - 1; ++i) {
      if (origValues[i] > origValues[i+1]) {
		[origValues[i], origValues[i+1]] = [origValues[i+1], origValues[i]]
        swapped = true;
      }
    }
  }
  while(swapped === true);
  return origValues
}

Answer 22

我喜欢

Answer 23

Answer 24

冒泡排序

/**
* @param {Array} arr 待排序数组
* @returns {Array}
*/
function bubbleSort(arr) {
     for (var i = 0, len = arr.length; i < len;  i++) {
          for (var j = i + 1;  j < len;  j++) {
               if (arr[i] > arr[j]) {
                    var temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
               }
          }
     }
     return arr;
}

时间复杂度（大O计数法）：O(n^2)

通常说的时间复杂度是指的最坏的情况。具体解析如下：

• 两层for循环，假如每一次if条件都满足，就是需要执行 n * (n-1) * 3 次， 取最高次项后常数系数变为1之后可以得到时间复杂度为 n^2

Answer 25

时间复杂度： O(n2)
let arr = [ 2, 3, 4, 44, 9, 4, 3, 2, 5, 1, 65, 2, 3, 6 ]
	for(let i = 0; i < arr.length; i++ ) {
		for(let j = i + 1; j < arr.length; j++) {
			if(arr[i] > arr[j]) {
				let beforeVar = arr[i]
				arr[i] = arr[j]
				arr[j] = beforeVar
			}
		}	
	} 

Answer 26

补充一个

function bubbleSort2(arr) {
    let low = 0;
    let high = arr.length - 1;
    let temp, j;

    while (low < high) {
        // 正排找最大
        for (j = low; j < high; ++j) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        --high;

        // 反排找最小
        for (j = high; j > low; --j) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        ++low;
    }
    console.log(arr);
}

Answer 27

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log(arr);
}

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    console.log(arr);
}

Answer 28

刚好这有一篇文章解答了今天面试题https://www.jianshu.com/p/5d44186b5263