关于排序:冒泡排序

冒泡排序思维

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

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

  算法形容

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)
• 稳定性：稳固