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

[zeroone001]

时间复杂度： 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)));

[admin00001]

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

[Ray-56]

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);
}

[Ray-56]

补充一个

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);
}

[xbcc123]

时间复杂度： 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
			}
		}	
	} 

[Haru1990]

冒泡排序

/**
* @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

[ChuYang-FE]

[fengjinlong]

我喜欢

[xxxsf]

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
}

[haiifeng]

时间复杂度： 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

[hengliyin]

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 这个改良算法能解释一下吗？

[lzbSun]

// 冒泡排序
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)

[ablikim915]

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)));

练个手

[chengshenghua]

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

[raven3005672]

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 这个改良算法能解释一下吗？

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

[dingLeiOnly]

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]];
       }
 }