第 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]

我喜欢

[xsf0105]

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

[mengsixing]

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

[MTStark]

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

[yuyueMidea]

长知识了~

[wwwxy80s]

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值

[longfeiyu127]

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

[Jesseszhang]

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

[lovelmh13]

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

[Gumplefik]

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

[cutie6]

```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; 循环条件不已经达到这个目的了吗？？

[fariellany]

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

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

[fariellany]

```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 标准的是 每次都是一次递减的，不管是不是存在部分冒泡好的

[523451928]

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

[gitwillsky]

另一种写法：

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

[ysyfff]

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

[tsnake520]

function bubbleSort(array) {
    if (!Array.isArray(array)) {
        throw new TypeError('train.js:bubbleSort() arguments is not Array');
    }

    let length = array.length,
         cycleIndex = Math.ceil(length / 8),
         complementNnumber = length % 8 - 1;

    for (let i = 0; i < length; i++) {
        let j = 0, 
             iteration = cycleIndex,
             startAt = complementNnumber;

        do {
            switch (startAt) {
                case 0: swap(j, j + 1), j++;
                case 7: swap(j, j + 1), j++;
                case 6: swap(j, j + 1), j++;
                case 5: swap(j, j + 1), j++;
                case 4: swap(j, j + 1), j++;
                case 3: swap(j, j + 1), j++;
                case 2: swap(j, j + 1), j++;
                case 1: swap(j, j + 1); j++;
            }

            startAt = 0;
        } while (--iteration > 0);
    }

    function swap(i, j) {
        if (array[i] > array[j]) {
            let temp = array[i];
            array[i] = array[j],
            array[j] = temp;
        }
    }

    return array;
}

[tchen-l]

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

这篇文章里面的 break 应该换成 continue

[Soyn]

const getRandomArray = (max = 100, len = 10) => {
  return Array.from(new Array(len)).map(() => Math.floor(Math.random() * max));
};

const solution = (a = []) => {
  let len = a.length;
  const t0 = performance.now();
  let swapped = false;
  do {
    swapped = false;
    for (let i = 1; i < len; i += 1) {
      if (a[i] < a[i - 1]) {
        [a[i], a[i - 1]] = [a[i - 1], a[i]];
        swapped = true;
      }
    }
  } while (swapped);
  const t1 = performance.now();
  console.log("time: ", t1 - t0);
  return a;
};

const solution1 = (a = []) => {
  let len = a.length;
  let swapped = false;
  const t0 = performance.now();
  do {
    swapped = false;
    for (let i = 1; i < len; i += 1) {
      if (a[i] < a[i - 1]) {
        [a[i], a[i - 1]] = [a[i - 1], a[i]];
        swapped = true;
      }
    }
    len -= 1;
  } while (swapped);
  const t1 = performance.now();
  console.log("time: ", t1 - t0);
  return a;
};

const solution2 = (a = []) => {
  let len = a.length;
  const t0 = performance.now();
  do {
    let newLen = 0;
    for (let i = 1; i < len; i += 1) {
      if (a[i] < a[i - 1]) {
        [a[i], a[i - 1]] = [a[i - 1], a[i]];
        newLen = i;
      }
    }
    len = newLen;
  } while (len > 1);
  const t1 = performance.now();
  console.log("time: ", t1 - t0);
  return a;
};

const a = getRandomArray(10000, 1000);
solution(a.slice());
solution1(a.slice());
solution2(a.slice());

Reference

• Bubble Sort

[jackluson]

Tip:

1. 冒泡则是在每一层遍历过程中找出最大的那个数（通过相邻比较，移动）
2. 算法复杂度：O(n2)， 可以通过空间换取时间方法--记录每一次遍历的第二大数索引，下一次遍历从第二大数索引位置开始遍历

let arr = [10, 80, 40, 60, 30, 90, 40, 50, 85];

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length - 1; 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]];
      }
    }
  }
};

const bubbleSortPlus = (arr) => {
  let second_max_pos = 0; // 存储每次遍历的第二大数索引
  for (let i = 0; i < arr.length - 1; i++) {
    let j = second_max_pos; // 从每次遍历之后的第二大数的索引开始遍历
    second_max_pos = 0; // 每次第二层遍历开始前重置
    for (j; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        if (arr[j] > arr[second_max_pos]) {
          second_max_pos = j;
        }
      }
    }
  }
};

bubbleSortPlus(arr);

更多解析

[sionnigjt]

function bubbleSort1(array) {
    //常规冒泡排序
    for (let i = 0; i < array.length; i++) {
        for (let j = i; j < array.length - 1; j++) {
            if (array[j] > array[j + 1]) {
                array[j + 1] = array[j + 1] ^ array[j]
                array[j] = array[j + 1] ^ array[j]
                array[j + 1] = array[j + 1] ^ array[j]
            }
        }

    }

}
function bubbleSort2(array) {
    //思路 :寻找每一次冒泡排序后最后一次交换的下标,减少排序次数
    let i = array.length - 1;
    while (i > 0) {
        let index = 0
        for (let j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                index=j
                array[j + 1] = array[j + 1] ^ array[j]
                array[j] = array[j + 1] ^ array[j]
                array[j + 1] = array[j + 1] ^ array[j]
            }
            
        }
        i = index;
    } 
}
let array = [1, 3, 2, 4, 11, 23, 3, 35, 7, 8,"2",'2',[5],(1),{"6":1}]
bubbleSort2(array)
console.log(array);

输出
[ 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 8, 11, 23, 35, { '6': 1 } ]
所以为啥??[5]不见了

[AKclown]

// 优化版本

function  sort(arr[]){
  for( int i = 0;i < arr.length - 1 ; i++ ){
          boolean isSort = true; // 关键
          for( int j = 0;j < arr.length - 1 - i ; j++ ){
              int temp = 0;
              if(arr[j] < arr[j + 1]){
                  temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
                  isSort = false;
              }
          }
          if(isSort){
              break;
          }
      }
}