交换排序

交换排序

通过比较关键字，然后交换

1. 冒泡排序

• 时间复杂度 O(n^2)
• 思路：
  1. 两两比较，大的那个放在最右边，比较到最末尾之后，最右边 即 最大
  2. 第二轮的比较中，将最大的排开，即 len -= 1，后面几轮也同样如此
  3. 最大的那个就会像冒泡一样，一个一个像最右靠

function BubbleSort(list) {
  let i, len, temp;

  for (len = list.length; len > 0; --len) {
    // 每次循环都会让一个当前数列中的最大值冒泡到最右边，即 下一次循环 最右边的数 无需比较，所以 len 每次循环都递减一次
    for (i = 0; i < len - 1; ++i) {
      if (list[i] > list[i + 1]) {
        temp = list[i + 1];
        list[i + 1] = list[i];
        list[i] = temp;
      }
      // console.log(++count);
    }
  }
}

2. 快速排序

• 时间复杂度 O(n logn)，空间复杂度(log n)
• 思路：
  1. 任取一个元素(一般为第一个)为 中心，
  2. 比 其 小的都放左边，大的都放右边，形成左右 两个 子数列
  3. 对 各子数列 重复上述两步，直到每个子表元素只剩下一个

function QuickSork(list, low, high) {
  if (low >= high) {
    return;
  }
  let i = low;
  let j = high;
  let temp = list[low];
  while (i < j) {
    while (i < j && temp <= list[j]) {
      --j;
    }
    list[i] = list[j];
    while (i < j && temp >= list[i]) {
      ++i;
    }
    list[j] = list[i];
  }
  list[i] = temp;
  QuickSork(list, low, i - 1);
  QuickSork(list, i + 1, high);
}