前言

排序的常用算法 之 有事没事敲一遍，下面的图片来自百度图片；

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 1,冒泡排序（两两对比）
function bubbleSort(arr) {
  if (!arr.length) return arr;
  const len = arr.length;

  for (let i = 0; i < len; i++) {
    let flag = true;
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 互换位置
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        // 只要对比还有交换，就证明排序还没结束
        flag = false;
      }
    }
    if (flag) return arr;
  }
  return arr;
}

// console.log(bubbleSort([78, 6, 7, 3, 9, 45, 10, 8]))

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 选择排序(选最小值)
function selectSort(arr) {

  if (!arr.length) return arr;

  const len = arr.length;
  let minIndex;

  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i; j < len; j++) {
      // 还有值比当前最小值小
      if (arr[minIndex] > arr[j]) {
        // 重新赋值minIndex
        minIndex = j;
      }
    }

    // 最小值index变了， 把minIndex位置上的值替换掉
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }

  }

  return arr
}

// console.log(selectSort([78, 6, 7, 3, 9, 45, 10, 8]))

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 插入排序(范围排序)
function insertSort(arr) {
  if (!arr.length) return arr;

  // 缓存数组长度
  const len = arr.length;
  // temp 用来保存当前需要插入的元素
  let temp;
  for (let i = 0; i < len; i++) {
    // 范围
    temp = arr[i];
    let j = i;
    // 判断前一个数据是否比后面一位大
    while (j > 0 && arr[j - 1] > temp) {
      // 大的数据向后移动位置，让出一个空位用来放小值
      arr[j] = arr[j - 1];
      j--;
    }
    // 循环让位，让出来的空位就是这个 待插入值 的位置
    arr[j] = temp;

  }


  return arr;
}

// console.log(insertSort([2, 6, 7, 3, 9, 45, 10, 0]))

归并排序

归并排序是对分治思想的典型应用。

  • 分解子问题
  • 求解每个子问题
  • 合并子问题的解，得出大问题的解

看图理解

图一

图二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 把数组平分拆分成最小单元，再合并，合并过程中排序，合并结束排序结束
// 拆分 
function mergeSort(arr) {

  if (!arr && !arr.length) return

  const len = arr.length;

  // 边界
  if (arr.length === 1) return arr;
  // 中点
  const center = Math.floor(len / 2);

  // 拆分左边
  const leftArr = mergeSort(arr.slice(0, center));
  // 拆分右边
  const rightArr = mergeSort(arr.slice(center, len));

  return mergeArr(leftArr, rightArr);
}

console.log(mergeSort([2, 4, 6, 3, 4, 59, 12, 32, 7, 21])); // [ 2,  3,  4,  4, 6, 7, 12, 21, 32, 59 ]

// 合并两个有序数组(小到大)
function mergeArr(arr1, arr2) {
  if (!arr1 && !arr2) return null;
  let i = 0, j = 0; // 声明指针

  // 缓存数组长度
  let len1 = arr1.length;
  let len2 = arr2.length;

  // 结果数组
  let res = [];

  // 合并
  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i]);
      i++;
    } else {
      res.push(arr2[j]);
      j++;
    }
  }

  // 剩下的数据直接放入
  if (i < len1) {
    return res.concat(arr1.slice(i));
  } else {
    return res.concat(arr2.slice(j));
  }

}

more

排序算法还有很多，什么时候敲了再更新。