陈恒承

交换排序

冒泡排序

算法思想，每一轮排序（从小到大），从后往前遍历比较，把最小值一步步交换到相应的位置。

时间复杂度: n(n-1)/2

冒泡排序算法的优化改进 - Coding 的文章 - 知乎
https://zhuanlan.zhihu.com/p/51479010

从前往后遍历

function bubbleSort(nums) {
  // 最外层的代表排序几轮， nums.length 轮
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        let temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
  console.log(nums.slice());
}

从后往前遍历

function bubbleSort(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = nums.length - 1; j > i; j--) {
      if (nums[j] < nums[j - 1]) {
        let temp = nums[j - 1];
        nums[j - 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
  console.log(nums);
}

function floatSortTow(nums) {
  // 有一个标准位，检测这一趟是否需要交换，如果不需要交换，那么代表排序好了。

  let done = false;
  let compare_count = 0;
  let round = 0; // 遍历趟数

  let length = nums.length;
  while (!done) {
    done = true;
    for (let i = 0; i < length - 1; i++) {
      compare_count++;

      if (nums[i] > nums[i + 1]) {
        // 差不多---运用位运算进行交换
        nums[i] = nums[i] ^ nums[i + 1];
        nums[i + 1] = nums[i] ^ nums[i + 1];
        nums[i] = nums[i] ^ nums[i + 1];
        done = false; // 发生了交换，数组还没排好序
      }
    }
    length--; // 最后一个元素已归位，下一趟排序无需进行比较
    console.log("第%d趟：%o", ++round, ...nums);
  }
  console.log("一共比较了%d次", compare_count);
  console.log(nums);
}

floatSortTow([2, 7, 3, 1, 3, 1, 1, 9]);

冒泡排序优化要点:

• 减少排序比较次数
• 已经排好的，就不必要再排了，设置标识.