排序算法总结-冒泡排序

思路

两个数比较大小，较大的数下沉，较小的数冒起来。

var arr=[9,3,1,5,4,6,2,8,7];
function bubbleSort(arr){
  for(var i=0;i<arr.length-1;i++){
    for(var j=0;j<arr.length-i-1;j++)
    {
      if(arr[j]>arr[j+1]){
        var temp = arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
      }
    }
  }}
bubbleSort(arr);//arr新值[1, 2, 3, 4, 5, 6, 7, 8, 9]

外循环第五次后，数组已经排好序了。第6、7、8次是浪费。
解决思路：当本次循环没有交换元素时，跳出循环。

优化版冒泡

var arr = [9, 3, 1, 5, 4, 6, 2, 8, 7];
function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var swap = false;//初始设置交换状态为fales
    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap = true;//交换过后设置交换状态为true
      }
    }
    if (!swap) {//如果交换状态为false,跳出循环
      break;
    }
  }
}
bubbleSort(arr);//arr新值[1, 2, 3, 4, 5, 6, 7, 8, 9]

如果执行某某次内层循环时没有交换，说明已经排好序了，跳出外层循环，冒泡结束。