Loveyless的学习笔记

Appearance

Return to top
On this page

冒泡排序(Bubble Sort)

思路

  1. 使用前一个值比后一个值，如果前>后,则位置互换
  2. 第一个数要一直比到最后一个数，第一个数下标为 0，最后一个为 length-1
  3. 依次比较，但是第一次比较最大的值就会被放到最后，下一次比较不需要比最后一个值,以此类推
  4. 就这样以此类推开始比较

alt

js
比如一个数组
let arr = [5,3,6,3,9]; // length为5

// 第一次比四趟
[5,3,6,3,9]
  5比3 换位得 [3,5,6,3,9]
    5比6 不换得 [3,5,6,3,9]
      6比3 换位得 [3,5,3,6,9]
        6比9 不换得 [3,5,3,6,9]

// 第二次比三趟 (arr[length-1]已经被换位最大的9
[3,5,3,6,9]
  3比5 不换得 [3,5,3,6,9]
    5比3 换位得 [3,3,5,6,9]
      5比6 不换得 [3,3,5,6,9]

// 第三次比二趟 (arr[length-2]已经被换位最大的6

// 第四次比一趟 (arr[length-2]已经被换位最大的5

可知长度为 n 的数组需要比 n-1 次 需要比较的次数和比较的趟数成反比

实现

js
function bubbleSort(array){

  let arr = array.concat();

  //比较length-1次
  for(let i = 0; i < arr.length - 1; i++){

    //和次数成反比的趟数j < arr.length - 1 - i
    //第一个i为0所以正好为反比
    for(let j = 0; j < arr.length - 1 - i; j++){

      //循环比较
      if (arr[j] > arr[j + 1]) {
        let temp = null;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }

    }

  }

  return arr;

}


----------测试代码----------

// let a = [3, 2, 1, 4, 5]
let a = Array(10).fill(1).map(() => {
return Math.floor(Math.random() * (Math.floor(1000) - Math.ceil(0)) + Math.ceil(0))
})

console.log('初始值', a);
console.time();
let b = sort(a);
console.timeEnd();
console.log('排序后', b); //结果不会去重

简洁版

ts
let arr323 = [53, 2, 2, 6, 63, 312, 23, 6, 74, 6, 2, 8, 856, 85, 75, 4, 7, 8, 9, 9];

function sort222(arr: Array<number>): Array<number> {
  if (!arr.length) return null;
  //比较length-1次
  for (let i = 0; i < arr.length - 1; i++) {
    //和次数成反比的趟数j < arr.length - 1 - i
    //第一个i为0所以正好为反比
    for (let k = 0; k < arr.length - i - 1; k++) {
      if (arr[k] > arr[k + 1]) {
        [arr[k], arr[k + 1]] = [arr[k + 1], arr[k]];
      }
    }
  }
}

sort222(arr323);
console.log(arr323);

优化

如果当第 n 次后并没有一趟换位 那么说明数组已经排序完毕了 就不需要继续下一次 所以每次开始时假设排序已经结束

js
function bubbleSort(array){
  let arr = array.concat();

  //排序结束了吗？
  let isSort = false;

  for(let i = 0; i < arr.length - 1; i++){

    console.log(`第${i+1}次`);

    // 每一趟之前都假设这趟不用换了 因为已经排好了
    isSort = true;
    for(let j = 0; j < arr.length - 1 - i; j++){

      console.log(`第${i+1}次的第${j+1}趟`);

      if (arr[j] > arr[j + 1]) {
        let temp = null;
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        //还假设排完呢 想得美
        isSort = false;
      }

    }

    //能走到这里说明没有一趟前一项大于后一项 也就是说一趟都没换成功 也就是说排序排完咯
    if (isSort) return arr;

  }

  return arr;

}



----------测试代码----------


// let a = [3, 2, 1, 4, 5]
let a = Array(5).fill(1).map(() => {
return Math.floor(Math.random() * (Math.floor(1000) - Math.ceil(0)) + Math.ceil(0))
})

console.log('初始值', a);
console.time();
let b = sort(a);
console.timeEnd();
console.log('排序后', b); //结果不会去重

然后我们就会发现有时候会少排 1 次或者多次

go 语言实现

go
func Bubbling(arr []int) []int {

	swi := false

	for i := 0; i < len(arr)-1; i++ {

		for j := 0; j < len(arr)-i-1; j++ {
			//如果前一个比后一个大 则换位
			if arr[j] > arr[j+1] {
				swi = true
				var temp int
				temp = arr[j+1]
				arr[j+1] = arr[j]
				arr[j] = temp
			}
		}

		if swi {
			break
		}

	}

	return arr

}