排序相关算法

2019年08月08日

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。

特点：

 1function sort(arr) {
 2  const len = arr.length;
 3  for (let i = 0; i < len; i++) {
 4    let min = i;
 5    for (let j = i; j < len; j++) {
 6      if (less(arr, j, min)) min = j;
 7    }
 8    exch(arr, i, min);
 9  }
10}

插入排序

循环数组，保证当前索引左边的所有元素都是有序的，比较当前索引和前面有序元素，将此索引插入至合适的位置。

特点为：对部分有序的数组排序速度较快

1function sort(arr) {
2  const len = arr.length;
3  for (let i = 1; i < len; i++) {
4    for (let j = i; j > 0 && less(arr, j, j - 1); j--) {
5      exch(arr, j, j - 1);
6    }
7  }
8}

归并排序

递归地将数组分成两半分别排序，然后再将结果归并起来。

有点是保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；缺点是所需的额外空间和 N 成正比。

 1// 辅助数组
 2let aux;
 3
 4function merge(arr, lo, mid, hi) {
 5  // copy
 6  for (let k = lo; k <= hi; k++) {
 7    aux[k] = arr[k];
 8  }
 9
10  let i = lo,
11    j = mid + 1;
12  for (let k = lo; k <= hi; k++) {
13    if (i > mid) {
14      // 左半边用尽
15      arr[k] = aux[j++];
16    } else if (j > hi) {
17      // 右半边用尽
18      arr[k] = aux[i++];
19    } else if (less(aux, i, j)) {
20      // 左边小
21      arr[k] = aux[i++];
22    } else {
23      // 右边小
24      arr[k] = aux[j++];
25    }
26  }
27}
28
29function _sort(arr, lo, hi) {
30  if (lo >= hi) return;
31  if (lo + 1 === hi) {
32    if (less(arr, hi, lo)) exch(arr, hi, lo);
33    return;
34  }
35
36  const mid = lo + Math.floor((hi - lo) / 2);
37  _sort(arr, lo, mid);
38  _sort(arr, mid + 1, hi);
39  merge(arr, lo, mid, hi);
40}
41
42function sort(arr) {
43  const len = arr.length;
44
45  // 初始化辅助数组
46  aux = new Array(len);
47
48  _sort(arr, 0, len - 1);
49}

快速排序

通过切分将数组分成两个子数组，切分后左半边数组不大于切分点，右半边数组不小于切分点，然后再递归地排序。

特点：

 1// 打乱数组
 2function random(arr) {
 3  const len = arr.length;
 4  for (let i = 0; i < len; i++) {
 5    exch(arr, i, Math.floor(Math.random() * len));
 6  }
 7}
 8
 9// 切分
10function partition(arr, lo, hi) {
11  let i = lo,
12    j = hi + 1;
13  while (true) {
14    while (less(arr, ++i, lo)) {
15      if (i === hi) break;
16    }
17    while (less(arr, lo, --j)) {
18      if (j === lo) break;
19    }
20    if (i >= j) break;
21    exch(arr, i, j);
22  }
23  exch(arr, lo, j);
24  return j;
25}
26
27function _sort(arr, lo, hi) {
28  if (lo >= hi) return;
29  if (lo + 1 === hi) {
30    if (less(arr, hi, lo)) exch(arr, hi, lo);
31    return;
32  }
33
34  // 切点
35  const p = partition(arr, lo, hi);
36  _sort(arr, lo, p - 1);
37  _sort(arr, p + 1, hi);
38}
39
40function sort(arr) {
41  random(arr);
42  const len = arr.length;
43  _sort(arr, 0, len - 1);
44}

堆排序

 1// 堆下沉
 2function sink(arr, i, len) {
 3  while (i * 2 + 1 < len) {
 4    // 下沉时和两个子节点中较大的一个交换
 5    let j = i * 2 + 1;
 6    if (j + 1 <= len - 1 && less(arr, j, j + 1)) j = j + 1;
 7
 8    if (less(arr, i, j)) {
 9      exch(arr, i, j);
10      i = j;
11    } else {
12      break;
13    }
14  }
15}
16
17function sort(arr) {
18  const len = arr.length;
19
20  // 堆有序
21  for (let k = Math.floor(len / 2); k >= 0; k--) {
22    sink(arr, k, len);
23  }
24
25  // 挑选最大值
26  let n = len;
27  while (n > 1) {
28    // 交换第一个和最后一个元素，此时最后一个元素肯定就是最大值了
29    exch(arr, 0, --n);
30    // 堆长度减一后下沉
31    sink(arr, 0, n);
32  }
33}