frenchleave

JavaScript实现排序算法合集

2020/10/20 JavaScriptAlgorithm

参考文章：

排序算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

来自 百度百科-排序算法稳定性 (opens new window)

# 排序算法对照表

image-default

# 冒泡排序

参考文章：面试官：说说你对冒泡排序的理解？如何实现？应用场景？ (opens new window)

思路分析

  1. 相邻两个数两两相比，arr[j]跟arr[j+1]比，如果arr[j] > arr[j+1]，则将两个数进行交换，j++
  2. 重复以上步骤，第一趟结束后，最大数就会被确定在最后一位，这就是冒泡排序又称大（小）数沉底
  3. i++，重复以上步骤，直到i = len - 1结束，排序完成
image-default

实现

/**
 * 稳定 O(n²) O(1)
 */
Array.prototype.bubbleSort = function () {
  const len = this.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        [this[j], this[j + 1]] = [this[j + 1], this[j]];
      }
    }
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].bubbleSort();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

优化：对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程，可以设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置，由于pos位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到pos位置即可

Array.prototype.bubbleSort1 = function () {
  let i = this.length - 1; // 初始时,最后位置保持不变
  while (i > 0) {
    let pos = 0; // 每趟开始时,无记录交换
    for (let j = 0; j < i; j++) {
      if (this[j] > this[j + 1]) {
        [this[j], this[j + 1]] = [this[j + 1], this[j]];
        pos = j; // 记录最后交换的位置
      }
    }
    i = pos; // 为下一趟排序作准备
  }
  return this;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

应用场景：冒泡排的核心部分是双重嵌套循环，时间复杂度是O(n²)，相比其它排序算法，这是一个相对较高的时间复杂度，一般情况不推荐使用，由于冒泡排序的简洁性，通常被用来对于程序设计入门的学生介绍算法的概念

# 选择排序

参考文章：面试官：说说你对选择排序的理解？如何实现？应用场景？ (opens new window)

思路：数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

image-default

实现

/**
 * 不稳定 O(n²) O(1)
 */
Array.prototype.selectionSort = function () {
  const len = this.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (this[j] < this[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [this[i], this[minIndex]] = [this[minIndex], this[i]];
    }
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].selectionSort();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

应用场景：和冒泡排序一致，相比其它排序算法，这也是一个相对较高的时间复杂度，一般情况不推荐使用

# 插入排序

参考文章：面试官：说说你对插入排序的理解？如何实现？应用场景？ (opens new window)

思路

  1. 从第二位开始遍历
  2. 当前数（第一趟是第二位数）与前面的数依次比较，如果前面的数大于当前数，则将这个数放在当前数的位置上，当前数的下标减1，
  3. 重复以上步骤，直到当前数不大于前面的某一个数为止，这时，将当前数，放到这个位置，1-3步就是保证当前数的前面的数都是有序的，内层循环的目的就是将当前数插入到前面的有序序列里
  4. 重复以上3步，直到遍历到最后一位数，并将最后一位数插入到合适的位置，插入排序结束。
image-default

实现

/**
 * 稳定 O(n²) O(1)
 */
Array.prototype.insertionSort = function () {
  const len = this.length;
  for (let i = 1; i < len; i++) {
    const pivot = this[i];
    let j = i;
    while (j > 0 && this[j - 1] > pivot) {
      this[j] = this[j - 1];
      j--;
    }
    this[j] = pivot;
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].insertionSort();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

应用场景：插入排序时间复杂度是O(n²)，适用于数据量不大，算法稳定性要求高，且数据局部或整体有序的数列排序

# 归并排序

参考文章：面试官：说说你对归并排序的理解？如何实现？应用场景？ (opens new window)

思路

归并排序就是递归得将原始数组递归对半分隔，直到不能再分（只剩下一个元素）后，开始从最小的数组向上归并排序

  1. 向上归并排序的时候，需要一个暂存数组用来排序
  2. 将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移
  3. 直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里
  4. 再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。
image-default

递归版本（长度为n的数组，mergeSort方法调用2n-1次，所以长度超过1500在firefox上会发生栈溢出的错误）

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}

/**
 * 稳定 O(nlogn) O(n)
 */
Array.prototype.mergeSort = function () {
  const len = this.length;
  if (len < 2) {
    return this;
  }
  const middle = Math.floor(len / 2);
  const left = this.slice(0, middle);
  const right = this.slice(middle);
  return merge(left.mergeSort(), right.mergeSort());
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].mergeSort();
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

分治法：速度仅次于快速排序，为稳定排序算法

function merge(arr, temp, left, middle, right) {
  // 通过右边数组的起始位置得到左边数组的结束位置
  const leftEnd = middle - 1;
  // 如果‘指针’没有越界
  while (left <= leftEnd && middle < right) {
    // 如果左边数组第一个元素比右边数组第一个元素大
    if (arr[left] > arr[middle]) {
      // 将右边数组最小的放入有序数组 temp（初始值为空)
      temp[left + middle - leftEnd - 1] = arr[middle++];
    } else {
      // 将左边数组最小的放入有序数组 temp（初始值为空)
      temp[left + middle - leftEnd - 1] = arr[left++];
    }
  }
  // 如果左边数组放完了，右边数组还有元素
  while (left > leftEnd && middle < right) {
    // 那么依次将右边数组剩余的元素放入 temp
    temp[left + middle - leftEnd - 1] = arr[middle++];
  }
  // 如果右边数组放完了，左边数组还有元素
  while (left <= leftEnd && middle >= right) {
    // 那么依次将左边数组剩余的元素放入 temp
    temp[left + middle - leftEnd - 1] = arr[left++];
  }
}

/**
 * 稳定 O(nlogn) O(n)
 */
Array.prototype.mergeSort = function () {
  // 将每个元素看作是相邻的数组 长度为1
  let length = 1;
  const len = this.length;
  let i; // 迭代深度
  const temp = []; // 定义一个额外的数组用作排序交换
  for (i = 0; 2 ** i < len; i++, length *= 2) { // 每次跳过的长度翻倍
    const even = i % 2 === 0; // 复用 arr 和 temp 来回赋值
    // 左边数组起始位置 left 从0开始
    for (let left = 0; left < len; left += 2 * length) {
      // 右边数组起始位置middle就是：left + 一个数组长度step（但是不要超过len）
      const middle = left + length < len ? left + length : left;
      // 右边界 right 就是 left + 两个数组长度
      const right = left + (2 * length) < len ? left + (2 * length) : len;
      // 合并每两个相邻的数组
      merge(even ? this : temp, even ? temp : this, left, middle, right);
    }
  }
  if (i % 2 === 0) {
    return this; // 返回 this
  }
  return temp; // 返回 temp
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].mergeSort();
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

WARNING

上面两种实现方式都不是原地算法（in-place），所以使用时需要额外定义变量接收排序后的结果数组

原地算法实现

function merge(arr, left, middle, right) {
  // 通过右边数组的起始位置得到左边数组的结束位置
  const leftEnd = middle - 1;
  // 如果‘指针’没有越界
  while (left <= leftEnd && middle < right) {
    // 如果左边数组第一个元素比右边数组第一个元素大
    if (arr[left] > arr[middle]) {
      // 直接在原地交换，将右边数组最小的放入左边的有序数组
      // 并且right指针右移，left指针不变
      arr.splice(left, 0, ...arr.splice(middle++, 1));
    } else {
      // 否则左边的数比右边的数小，left指针右移
      left++;
    }
  }
}

/**
 * 稳定 O(nlogn) O(n)
 */
Array.prototype.mergeSort = function () {
  // 将每个元素看作是相邻的数组 长度为1
  let length = 1;
  const len = this.length;
  let i; // 迭代深度
  for (i = 0; 2 ** i < len; i++, length *= 2) { // 每次跳过的长度翻倍
    // 左边数组起始位置 left 从0开始
    for (let left = 0; left < len; left += 2 * length) {
      // 右边数组起始位置middle就是：left + 一个数组长度step（但是不要超过len）
      const middle = left + length < len ? left + length : left;
      // 右边界 right 就是 left + 两个数组长度
      const right = left + (2 * length) < len ? left + (2 * length) : len;
      // 合并每两个相邻的数组
      merge(this, left, middle, right);
    }
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].mergeSort();
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
class MergeSort {
  static temp = []

  static sort(nums) {
    const n = nums.length;
    this.temp = new Array(n);
    this.doSort(nums, 0, n - 1);
    return nums;
  }

  static doSort(nums, left, right) {
    if (left === right) return;
    const mid = left + ((right - left) >> 1);
    this.doSort(nums, left, mid);
    this.doSort(nums, mid + 1, right);
    this.merge(nums, left, mid, right);
  }

  static merge(nums, left, mid, right) {
    for (let i = left; i <= right; i++) {
      this.temp[i] = nums[i];
    }
    let i = left; // 第一个数组的左端点
    let j = mid + 1; // 第二个数组的左端点
    for (let p = left; p <= right; p++) {
      if (i === mid + 1) {
        // 左半边数组已全部被合并
        nums[p] = this.temp[j++];
      } else if (j === right + 1) {
        // 右半边数组已全部被合并
        nums[p] = this.temp[i++];
      } else if (this.temp[i] > this.temp[j]) {
        nums[p] = this.temp[j++];
      } else {
        nums[p] = this.temp[i++];
      }
    }
  }
}

MergeSort.sort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]);
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

# 快速排序

参考文章：面试官：说说你对快速排序的理解？如何实现？应用场景？ (opens new window)

快速排序的思想：选一个数作为基数（这里我选的是第一个数），大于这个基数的放到右边，小于这个基数的放到左边，等于这个基数的数可以放到左边或右边，看自己习惯，这里我是放到了左边。一趟结束后，将基数放到中间分隔的位置，第二趟将数组从基数的位置分成两半，分割后的两个的数组继续重复以上步骤，选基数，将小数放在基数左边，将大数放到基数的右边，再分割数组...，直到数组不能再分为止，排序结束。

image-default

根正苗红的快排实现：

/**
 * 不稳定 O(nlogn) O(logn)
 */
Array.prototype.quickSort = function () {
  const sort = (arr, left = 0, right = arr.length - 1) => {
    // 如果左边的索引大于等于右边的索引说明整理完毕
    if (left >= right) return;
    let i = left;
    let j = right;
    const pivot = arr[i]; // 取无序数组第一个数为基准值
    while (i < j) { // 把所有比基准值小的数放在左边 大的数放在右边
      // 从后往前找到一个比基准值小的数
      while (i < j && arr[j] >= pivot) {
        j--;
      }
      // 小放在左边 如果没有比基准值小的就将自己赋值给自己（i等于j）
      arr[i] = arr[j];
      // 从前往后找到一个比基准值大的数
      while (i < j && arr[i] <= pivot) {
        i++;
      }
      // 大放在右边 如果没有比基准值大的就将自己赋值给自己（i等于j）
      arr[j] = arr[i];
    }
    arr[i] = pivot; // 将基准值放至中央位置完成一次循环（这时候j等于i）
    sort(arr, left, i - 1); // 将左边的无序数组重复上面的操作
    sort(arr, i + 1, right); // 将右边的无序数组重复上面的操作
  };
  sort(this);
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].quickSort();
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

应用场景：快速排序时间复杂度为O(nlogn)，是目前基于比较的内部排序中被认为最好的方法，当数据过大且数据杂乱无章时，则适合采用快速排序

另一种实现方式，每次剪切数组第一位作为基准（如果数组长度为小于等于1 则算是排好并返回该数组），循环剩下的，小的放进左边数组，大的放进右边数组并且把左边的和右边的再继续递归，并把左边数组和剪切的基准和右边的数组连接：


Array.prototype.quickSort = function () {
  const sort = (arr) => {
    if (arr.length <= 1) return arr;
    const left = [];
    const right = [];
    const pivot = arr[0]; // 基准元素
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] <= pivot) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...sort(left), pivot, ...sort(right)];
  };
  return sort(this);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 希尔排序

/**
 * 希尔排序是对直接插入排序的改进 又称缩小增量排序
 * 不稳定 O(n^(3/2)) O(1)
 */
Array.prototype.shellSort = function () {
  const len = this.length;
  for (let i = Math.floor(len / 2); i > 0; i = Math.floor(i / 2)) {
    for (let j = i; j < len; j++) {
      for (let k = j - i; k >= 0 && this[k] > this[k + i]; k -= i) {
        [this[k], this[k + i]] = [this[k + i], this[k]];
      }
    }
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].shellSort();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 堆排序

将数组构建成一个堆（通常是最大堆），然后不断地将堆顶元素（最大元素）与堆末尾的元素交换，然后重新调整堆结构，使得交换后的堆仍然满足堆的性质。这样，每次交换后，堆中的最大元素会被置于末尾，最终形成一个有序的数组。

首先通过heapify函数构建初始的最大堆。然后进行两个阶段的循环：第一个循环用于构建最大堆，从数组的中间位置开始，依次向前调用heapify函数，使得整个数组满足最大堆的性质；第二个循环用于不断地将堆顶元素与堆末尾元素交换，并重新调整堆，直到整个数组有序。

/**
 * 不稳定 O(nlogn) O(1)
 */
function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

Array.prototype.heapSort = function () {
  const len = this.length;
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(this, len, i);
  }
  for (let i = len - 1; i > 0; i--) {
    [this[0], this[i]] = [this[i], this[0]];
    heapify(this, i, 0);
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].heapSort();
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

# 计数排序

是一种非比较型的排序算法（还包括桶排序、基数排序）。计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。

计算频率时间复杂度为O(N)，有序输出结果的时间复杂度为O(N+k)，其中k是输入的整数范围。计数排序（CountingSort）的时间复杂度为O(N+k)，如果k很小，那么它就是O(N)。由于内存限制，当k相对较大时，我们将无法执行计数排序（CountingSort）的计数部分，因为我们需要存储k个整数出现的次数。

/**
 * 稳定 O(N+k) O(k)
 */
Array.prototype.countingSort = function () {
  const len = this.length;
  let max = this[0];
  let min = this[0];
  for (let i = 0; i < len; i++) {
    max = Math.max(max, this[i]);
    min = Math.min(min, this[i]);
  }
  const range = max - min + 1;
  // 值的范围
  const countArr = new Array(range).fill(0);
  const output = new Array(len);
  // 统计每个元素出现的次数
  for (let i = 0; i < len; i++) {
    countArr[this[i] - min]++;
  }
  // 小于等于this[i]的数出现的总次数
  for (let i = 1; i < range; i++) {
    countArr[i] += countArr[i - 1];
  }
  for (let i = len - 1; i >= 0; i--) {
    // 小于等于this[i]的数共countArr[this[i] - min]个，那么this[i]的位置最大就在"次数-1"处
    output[countArr[this[i] - min] - 1] = this[i];
    countArr[this[i] - min]--;
  }
  for (let i = 0; i < len; i++) {
    this[i] = output[i];
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].countingSort();
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

# 桶排序

将待排序的数据元素分散到不同的桶中，然后对每个桶内的元素进行排序，最后将所有桶的元素按顺序合并起来，形成有序数组。

首先，通过Math.min()和Math.max()函数找到数组中的最小值和最大值，然后确定需要的桶的数量。接着，创建一个数组buckets，用于存放不同的桶，以及将待排序元素分散到各个桶中。每个元素根据其值映射到相应的桶中。

然后，对每个桶内的元素进行排序，这里使用了插入排序作为每个桶内部的排序算法。对每个桶使用插入排序的原因是，桶的数量可能较小，而插入排序在小规模数据的排序上性能较好。 最后，将排序后的各个桶的元素按顺序合并到原始数组中，完成整个排序过程。

Array.prototype.bucketSort = function (bucketSize = 5) {
  if (this.length === 0) {
    return this;
  }
  const minValue = Math.min(...this);
  const maxValue = Math.max(...this);
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;

  const buckets = new Array(bucketCount);
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }
  for (let i = 0; i < this.length; i++) {
    const bucketIndex = Math.floor((this[i] - minValue) / bucketSize);
    buckets[bucketIndex].push(this[i]);
  }
  this.length = 0;
  for (let i = 0; i < bucketCount; i++) {
    buckets[i].insertionSort();
    this.push(...buckets[i]);
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].bucketSort();
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

# 基数排序

将待排序的非负整数按照个位、十位、百位等位数依次进行分配和收集，从低位到高位逐渐完成排序。

首先，通过getMaxDigit函数找到数组中最大元素的位数。然后，从个位开始到最高位，循环进行位数的分配和收集操作。 在每一轮循环中，创建一个桶列表bucketList，其中包含10个桶（0到9）。然后遍历数组中的每个元素，根据当前位数的值将元素放入对应的桶中。之后，将桶列表中的元素按顺序取出并拼接，更新原数组，以便进入下一轮循环。

最终，经过所有位数的循环，数组中的元素将会被依次排列成有序的序列。

function getMaxDigit(arr) {
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    max = Math.max(max, arr[i].toString().length);
  }
  return max;
}

function getDigitValue(num, digit) {
  return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
}

Array.prototype.radixSort = function () {
  const maxDigit = getMaxDigit(this);
  for (let digit = 0; digit < maxDigit; digit++) {
    const bucketList = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < this.length; i++) {
      const digitValue = getDigitValue(this[i], digit);
      bucketList[digitValue].push(this[i]);
    }
    bucketList.flat().forEach((el, i) => {
      this[i] = el
    })
  }
  return this;
};

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48].radixSort();
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
最近更新: 2023年12月04日 11:32:28

树的遍历(Traversal)