冒泡排序思维

  • 根本思维: 冒泡排序，相似于水中冒泡，较大的数沉下去，较小的数缓缓冒起来，假如从小到大，即为较大的数缓缓往后排，较小的数缓缓往前排。

  • 直观表白，每一趟遍历，将一个最大的数移到序列开端。

    算法形容

  1. 比拟相邻的元素，如果前一个比后一个大，替换之。
  2. 第一趟排序第1个和第2个一对，比拟与替换，随后第2个和第3个一对比拟替换，这样直到倒数第2个和最初1个，将最大的数挪动到最初一位。
  3. 第二趟将第二大的数挪动至倒数第二位
  4. 因而须要n-1趟；

代码实现(js)

function bubbleSort(nums) {  let length = nums.length;  for (let i = 0;i < length - 1;i++) {    console.log('第', i + 1, '趟');    for (let j = 0;j < length - 1 - i;j++) {      if (nums[j] > nums[j + 1]) {        let a = nums[j];        nums[j] = nums[j + 1];        nums[j + 1] = a;      }      console.log(nums);    }  }};bubbleSort([90, 89, 78, 67, 56, 45, 34, 23, 12]);

复杂度

  • 工夫复杂度:O(N*N)
  • 最好状况: O(N)
  • 最差状况:O(N*N)
  • 空间复杂度: O(1)
  • 稳定性：稳固