选择排序

1. 简单选择排序

时间复杂度 O(n^2)
思路：

从头到尾扫描数列，找出最小的，和第一个交换，然后剩余的重复如此

function SelectSort(list) {
  let i, j, k, temp;
  for (i = 0; i < list.length; ++i) {
    k = i;
    for (j = i + 1; j < list.length; ++j) {
      if (list[j] < list[k]) {
        k = j;
      }
    }
    temp = list[k];
    list[k] = list[i];
    list[i] = temp;
  }
}

2. 堆排序

实际上是完全二叉树

时间复杂度： O(n logn)，空间复杂度： O(1)
实现堆排序的问题：
1. 如何将一个无序数列创建成一个堆？
  - 完全二叉树中，最后一个非叶子节点是 n / 2
  - 实际上就是从非叶子节点倒叙，反复筛选的过程
2. 剩下元素如何调整成新堆？(利用筛选)
  
  输出堆顶后，以堆中最后元素代替，然后将其与左右孩子比较，并与其小者(或大者)交换，如此重复，直到代替元素又变成了叶子节点，将得到新的堆。该过程成为筛选
思路：创建大根堆，弹出堆头，并用堆尾替换堆头。(因为弹出，所以堆长度是在递减的)
1. 创建大根堆
  1. 先建立一个大根堆(因为大根堆的堆顶是最大的，可以让其和堆末交换，在当前数组中排序，无需新创建一个数组，大大减少了空间)
  2. 建立大根堆，其实就是从 n/2 处开始筛选大根。
2. 筛选堆
  1. 先保存根的临时位置
  2. 让临时位置与左右孩子比较值，并用最大的值的位置赋值给初始根
  3. 比较临时位置和初始根，如果不同，则表示初始根变了，那么交换两者的值
  4. 由于做了交换，说明刚刚才建好大根堆，所以要继续深入，检验初始根位置是否是最终的叶子位置
3. 排序堆
  1. 为了减少开辟空间，利用大根堆弹出的最大值与当前堆末尾值交换
  2. 又由于堆长度是递减的，所以可以当大根堆弹出的最大值不存在， len 递减

let len = list.length;
//创建堆
function CreatHeap(list) {
  let i;
  for (i = Math.floor(len / 2) - 1; i >= 0; --i) {
    SiftHeap(list, i); // i = 3
  }
  console.log("创建成堆：", list);
}

// 筛选堆
function SiftHeap(list, i) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let temp = i;

  if (left < len && list[i] <= list[left]) {
    i = left;
  }
  if (right < len && list[i] <= list[right]) {
    i = right;
  }

  if (temp != i) {
    swap(list, temp, i);
    SiftHeap(list, i);
  }
}
//排序堆
function HeapSort(list) {
  CreatHeap(list);
  while (len > 0) {
    swap(list, len - 1, 0);
    --len;
    SiftHeap(list, 0);
  }
  console.log("排序：", list);
}

function swap(list, a, b) {
  let temp = list[a];
  list[a] = list[b];
  list[b] = temp;
}

选择排序

选择排序

1. 简单选择排序

2. 堆排序

相关推荐