Another RayJune

优雅的 JavaScript 排序算法(Old Edition)

致力于优雅的可读性好的 JavaScript 排序算法代码。
转载请署名,优化总结这些代码和知识点消耗 RayJune 大量元气

Preface 前言

或许你会像我一样困惑:为什么我们需要这么多种排序算法呢?

可能这个来自 StackOverFlow 的回答可以为你答疑解惑(自己翻译的,如有错误请尽管提醒):

我们有这么多不同的排序算法是因为他们适用于不同种类的情况(即没有最完美的排序算法,只有适合某种情况的排序算法),比如:

  • 归并排序适用于排序关联的列表(因为它不需要获得像数组一样可以访问任何下标的数据的特性)
  • 堆排序非常适用于排序数组(并且被许多关系型数据库引擎用于内存中排序,或 polyphase merge sort ),它使用少量额外的空间,但是是非常可预测的(因为无论什么数据输入都是 O(n·log(n)) time),是数据库引擎中需要的排序算法。
  • 快速排序具有出色的平均排序性能(比 n·log(n)) time 还要快),也有最坏情况的 O(n²),它是大部分库的默认排序方式(如 JavaScript 的 array.sort() ),它的最坏情况是数据库引擎不用它的原因(即快速排序不是完美无缺的)。
  • 当你的数据元素接近排序完成时,插入排序是好的选择。而如果你要向一个排序的数组/列表中加入几个元素的话,插入排序同样很适合
  • 甚至是最被人吐槽的、低级的冒泡算法也有适合它的地方:如果你有一个很小的待排序列表,而你可以忍受它的 O(n²) 效率时,它简短的代码将会很合适。

Maybe you will wonder (just like me): Why do we need so many sorting algorithms?

I think this answer from StackOverFlow can handle it:

下面是该回答原文:

We have many different ones because they satisfy different sorting use-cases. Some examples:

  • Merge sort is useful for sorting linked lists.
  • Polyphase merge sort is useful if the sort set can’t fit into RAM.
  • Heapsort is very good for sorting arrays (and is used by many relational db engines for in-memory sorting, or for the memory part of polyphase merge sort). It uses little extra RAM and is very predictable, which is the sort of behavior you want in a db engine.
  • Quicksort has excellent average-case behavior - and poor worst-case behavior - and is the default sort for most sorting library implementations.Its bad worst-case behavior is why it isn’t used for db engines.
  • Insertion sort is good if you have a set that is almost sorted; it’s good if you have a sorted list that has a couple items added to it occasionally but then needs to be resorted.
  • Even the much-ridiculed (including by me) Bubble sort algorithm has its use case: if you have a very small sort set so you can stand its O(n²) average case and don’t want a lot of code - as it’s by far the shortest sort algorithm by simple count of code - it can be used.

https://www.quora.com/Why-do-we-need-so-many-sorting-algorithms

Style Guide 编程规范

文章中的代码均采用 eslint 规范代码,采用的是 Airbnb 的 ES5 JavaScript 编程规范

其中额外遵守的编程规范有:

  • 注重可读性变量名:如 preIndex, temp, size
  • 一目了然的函数结构
    function () {
      var …;

      function body

      return…;
    }
  • 在计算 len / 2 的取整时为了可读性选择了 Math.floor(len / 2),没有选择 len >> 1 和 parseInt(len / 2, 10)
  • 在能使用函数式编程的情况下提供函数式编程的写法:如抽出 swap 为一个函数
  • 注意区分 for 和 while 的使用场景,具体可以看这个问题的答案:
    https://stackoverflow.com/questions/39969145/while-loops-vs-for-loops-in-JavaScript
  • 为了简单直观,未使用 Array.isArray(),Object.prototype.toString.call(),typeOf , instanceOf 来检查 arr 是不是数组类型,默认 arr 就是数组类型
  • 使用三元运算符 ( ? : ) 来减少 if 的嵌套,提高代码可读性
  • 自增(++)和自减(–)运算符使用 += 和 -= 代替 (for 中的最后一个条件除外)
  • 遇到循环时,缓存 arr.length

本文中常使用 swap 函数,在这里提前列出来,以下就省略了。

1
2
3
4
5
6
7
function swap(arr, indexA, indexB) {
var temp;

temp = arr[indexA];
arr[indexA] = arr[indexB];
arr[indexB] = temp;
}

Bubble Sort 冒泡排序

concise explanation 简明解释

通过依次比较、交换相邻的元素(按照由小到大的顺序,如果符合这个顺序就不用交换),一次这样的循环可以得到一个最大值,n - 1 次这样的循环可以排序完毕。

properties 特性

  • Stable
  • Adaptive: O(n) when nearly sorted ( but not better than Insertion sort )
  • O(n²) comparisons and swaps
  • O(1) extra space

关于 but not better than Insertion sort:

Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

core concept 核心概念

  • 利用交换,将最大的数冒泡到最后
  • 使用缓存 postion 来优化
  • 使用双向遍历来优化

concrete steps 具体步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该是最大的数
  3. 针对所有的元素重复以上的步骤,除了最后一个(因为前面排序完毕时最后一个也默认排序好了);
  4. 重复 1~3 ,直到所有元素均排序完毕。

basic code 基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubbleSort(arr) {
var i;
var j;

for (i = arr.length - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));

position cache 缓存 pos

设置一标志性变量 pos ,用于记录每趟排序中最后一次进行交换的位置。
由于 pos 位置之后的记录均已交换到位,故在进行下一趟排序时 只要扫描到 pos 位置即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSort2(arr) {
var i = arr.length - 1; // initial value, for the first while & for loop
var pos;
var j;

while (i > 0) {
pos = 0;
for (j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
pos = j;
swap(arr, j, j + 1);
}
}
i = pos;
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort2(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

two-way loop 双向遍历

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,
我们可以 在每趟排序中进行正向和反向两遍冒泡
一次可以得到两个最终值(最大和最小) , 从而使外排序趟数几乎减少了一半

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 bubbleSort3(arr) {
var i;
var start = 0;
var end = arr.length - 1;

while (start < end) {
for (i = start; i < end; i++) { // positive direction to find biggest
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
end -= 1;
for (i = end; i > start; i--) { // negative direction to find smallest
if (arr[i - 1] > arr[i]) {
swap(arr, i - 1, i);
}
}
start += 1;
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort3(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

postion cache & two-way loop 结合前两种优化

前两种优化方式(缓存 pos、双向遍历)的结合:

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
function bubbleSort4(arr) {
var i;
var start = 0;
var end = arr.length - 1;
var startPos;
var endPos;

while (start < end) {
endPos = 0;
startPos = 0;
for (i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
endPos = i;
swap(arr, i, i + 1);
}
}
end = endPos;
for (i = end; i > start; i--) {
if (arr[i - 1] > arr[i]) {
startPos = i;
swap(arr, i - 1, i);
}
}
start = startPos;
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort4(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Ant Financial

来自于蚂蚁金服的一道面试题:

对于冒泡排序来说,能不能传入第二个参数(参数为函数),来控制升序和降序?(联想一下 array.sort() )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bubbleSort(arr, compareFun) {
var i;
var j;

for (i = arr.length - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (compareFun(arr[j], arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
}
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr, function smallToBig(a, b) {return a - b;}));
console.log(bubbleSort(arr, function bigToSmall(a, b) {return b - a;}));

如果你像我一样理解错了意思的话(理解成了,如何在冒泡排序中传入一个函数参数,并使用 array.sort() 方法来排序)的话,就有了下面的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bubbleSort(arr, compareFun) {
var i;
var j;
var temp;
var len = arr.length;

for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - 1 - i; j++) {
temp = arr.splice(j, 2).sort(compareFun); // 利用 array.sort() 进行函数式编程
arr.splice(j, 0, temp[0], temp[1]);
}
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr, function smallToBig(a, b) {return a - b;}));
console.log(bubbleSort(arr, function bigToSmall(a, b) {return b - a;}));

Selection Sort 选择排序

concise explanation 简明解释

每一次内循环遍历寻找最小的数,记录下 minIndex,并在这次内循环结束后交换 minIndex 和 i 的位置,重复这样的循环 n - 1 次即得到结果。

properties 特性

  • Not stable
  • Not adaptive: Whatever input, it’s always O(n²), very low performance
  • Θ(n²) comparisons (这里我认为写为 O(n²) 更准确,不过影响不大)
  • Θ(n) swaps: 注意,这里只有 n 次的交换,选择排序的唯一优点 (同上,O(n))
  • O(1) extra space

关于 Θ(n) swaps:

Selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

即就算是我们觉得最慢的选择排序,也有它的用武之地

core concept 核心概念

  • “可预测”的时间复杂度,什么进来都是 O(n²),但不 stable,唯一的优点是减少了 swap 次数。

concrete steps 具体步骤

  1. 在未排序序列中找到最小的元素,存放到已排序序列的起始位置(默认是 arr[0] );
  2. 从剩余未排序元素中继续寻找最小的元素;
  3. 将找到的最小元素放到已排序序列的末尾;再执行步骤 1 寻找下一个最小的元素
  4. 重复 1~3 ,直到所有元素均排序完毕。

basic code 基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function selectionSort(arr) {
var i;
var minIndex;
var j;
var len = arr.length;

for (i = 0; i < len - 1; i++) {
minIndex = i;
for (j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(selectionSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

maxIndex 找到最大值

如果你想在每次内循环中找到最大值并把其交换到数组的末尾(相比较 minIndex 有点麻烦),以下是实现的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function selectionSort2(arr) {
var i;
var maxIndex;
var j;

for (i = arr.length - 1; i > 0; i--) {
maxIndex = i;
for (j = i - 1; j >= 0; j--) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
swap(arr, i, maxIndex);
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(selectionSort2(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Insertion Sort 插入排序

concise explanation 简明解释

默认 a[0] 为已排序数组中的元素,从 arr[1] 开始逐渐往已排序数组中插入元素,从后往前一个个比较,如果待插入元素小于已排序元素,则已排序元素往后移动一位,直到待插入元素找到合适的位置并插入已排序数组。经过 n - 1 次这样的循环插入后排序完毕。

properties 特性

  • Stable
  • Adaptive: O(n) time when nearly sorted (better than bubble sort)
  • Very low overhead 非常低的开销
  • O(n²) comparisons and swaps
  • O(1) extra space

For its advantages (adaptive, low overhead, stable, O(n) time when nearly sorted), insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as shell sort or quick sort.

core concept 核心概念

  • 高性能(特别是接近排序完毕时的数组),低开销,且 stable
  • 利用二分查找来优化

concrete step 具体步骤

  1. 从第一个元素开始( arr[0] ),该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤 3 ,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤 2 ~ 5 ,直到所有元素均排序完毕。

basic code 基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function insertionSort(arr) {
var i;
var temp;
var preIndex;
var len = arr.length;

for (i = 1; i < len; i++) {
temp = arr[i];
preIndex = i - 1;
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + 1] = arr[preIndex]; // move back 1 unit
preIndex -= 1; // Don't forget preIndex--
}
arr[preIndex + 1] = temp;
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

binary search algorithm 二分查找算法

因为对于插入排序的优化方法是:二分查找优化,这里补充一下二分查找的算法的实现。

核心概念是:折半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function binarySearch(arr, value) {
var min = 0;
var max = arr.length - 1;
var mid;

while (min <= max) {
mid = Math.floor((min + max) / 2);
if (arr[mid] === value) {
return mid;
} else if(arr[mid] > value) {
max = mid - 1;
} else {
min = mid + 1;
}
}

return 'Not Found'; // or return -1;
}

// test
var arr = [1, 2, 3];
console.log(binarySearch(arr, 2)); // 1
console.log(binarySearch(arr, 4)); // Not Found

use binary search 使用二分查找

查找插入位置时使用二分查找的方式来优化性能:

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
function binaryInsertionSort(arr) {
var i; // means unsorted index
var temp;
var preIndex;
var min;
var max;
var mid;
var len = arr.length;

for (i = 1; i < len; i++) {
temp = arr[i];
min = 0;
max = i - 1;
while (min <= max) { // use binary search
mid = Math.floor((min + max) / 2);
if (arr[mid] <= temp) { // keep stable
min = mid + 1;
} else {
max = mid - 1;
}
}
for (preIndex = i - 1; preIndex >= min; preIndex--) {
arr[preIndex + 1] = arr[preIndex];
}
arr[min] = temp;
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(binaryInsertionSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Shell Sort 希尔排序

concise explanation 简明解释

希尔排序是插入排序的改进版,它克服了插入排序只能移动一个相邻位置的缺陷(希尔排序可以一次移动 gap 个距离),利用了插入排序在排序几乎已经排序好的数组的非常快的优点。
使用可以动态定义的 gap 来渐进式排序,先排序距离较远的元素,再逐渐递进,而实际上排序中元素最终位置距离初始位置远的概率是很大的,所以希尔排序大大提升了性能(尤其是 reverse 的时候非常快,想象一下这时候冒泡排序和插入排序的速度)。

而且希尔排序不仅效率较高(比冒泡和插入高),它的代码相对要简短,低开销(继承插入排序的优点),追求这些特点(效率要求过得去就好,代码简短,开销低,且数据量较小)的时候希尔排序是好的 O(n·log(n)) 算法的替代品

总而言之:希尔排序的性能优化来自增量队列的输入和 gap 的设定。

properties 特性

  • Not stable
  • Adaptive: O(n·log(n)) time when nearly sorted (And its reverse is very quick)
  • O(n^3/2) time as shown (for more details, check wikipedia Shellsort
  • O(1) extra space

关于 not stable:

我们知道, 单次直接插入排序是稳定的,它不会改变相同元素之间的相对顺序,但在多次不同的插入排序过程中,
相同的元素可能在各自的插入排序中移动
,可能导致相同元素相对顺序发生变化。因此, 希尔排序并不稳定

关于 worse-case time 有一点复杂:

The worse-case time complexity of shell sort depends on the increment sequence. For the increments 1 4 13 40 121…, which is what is used here, the time complexity is O(n3/2). For other increments, time complexity is known to be O(n4/3) and even O(n·log2(n)).

core concept 核心概念

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到 O(n) 的效率;
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

其中 gap(增量)的选择是希尔排序的重要部分。只要最终 gap 为 1 任何 gap 序列都可以工作。算法最开始以一定的 gap 进行排序。然后会继续以一定 gap 进行排序,直到 gap = 1 时,算法变为插入排序。

Donald Shell 最初建议 gap 选择为 n / 2 并且对 gap 取半直到 gap 达到 1 。虽然这样取可以比 O(n²) 类的算法(插入排序、冒泡排序)更好,但这样仍然有减少平均时间和最差时间的余地。
(关于优化 gap 的细节涉及到复杂的数学知识,我们这里不做深究,详细可以参考 wikipedia 上的页面

concrete step 具体步骤

  1. 先将整个待排元素序列分割成若干个子序列(由相隔某个 “gap (增量)”的元素组成的)分别进行直接插入排序, 比方说将[49, 38, 65, 97, 26, 13, 27, 49, 55, 4] 的数组拆分为”增量” gap = 10 / 2 的分组, 那么子分组分别为 (49, 4), (38, 55), (65, 49), (97, 27), (26, 13),排序后为:(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)
  2. 然后依次缩减增量再进行排序, gap = Math.floor(gap / 2)
  3. 待整个序列中的元素基本有序(gap = 1)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的。

basic code 基本实现

Donald Shell 的最初建议(gap = n / 2)版代码(方便理解):

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 shellSort(arr) {
var i;
var temp;
var preIndex;
var len = arr.length;
var gap = Math.floor(len / 2);

while (gap > 0) {
for (i = gap; i < len; i++) {
temp = arr[i];
preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
gap = Math.floor(gap / 2);
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Knuth’s increment sequence

常见的、易生成的、优化 gap 的序列方法(来自 Algorithms (4th Edition) ,有些更快的方法但序列不容易生成,因为用到了比较深奥的数学公式):

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
function shellSort(arr) {
var i;
var temp;
var preIndex;
var len = arr.length;
var gap = 1;

while (gap < len / 3) { // dynamic define gap (Knuth’s sequence)
gap = gap * 3 + 1;
}
while (gap > 0) {
for (i = gap; i < len; i++) {
temp = arr[i];
preIndex = i - gap;
while (preIndex >= 0 && arr[preIndex] > temp) {
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
gap = Math.floor(gap / 2);
}

return arr;
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Merge Sort 归并排序

concise explanation 简明解释

归并排序使用分而治之的思想,以折半的方式来递归/迭代排序元素,利用空间来换时间,做到了时间复杂度 O(n·log(n)) 的同时保持了排序元素的 stable,这让它在一些更考虑排序效率和稳定性,次考虑存储空间的场合非常适用(如数据库内排序,和堆排序相比,归并排序的 stable 是优点)。并且归并排序非常适合于列表排序

properties 特性

  • Stable (在 O(n·log(n)) time 的排序算法中,归并排序是唯一稳定的)
  • Not adaptive
  • O(n·log(n)) time
  • Θ(n) extra space for arrays 注意:归并排序需要额外的空间,这是它的不完美之处
  • O(log(n)) extra space for linked lists 归并排序非常适合列表的排序
  • Does not require random access to data 因为这个特点,归并排序很适合用来排序列表

If using Θ(n) extra space is of no concern, then merge sort is an excellent choice: It is simple to implement, and it is the only stable O(n·lg(n)) sorting algorithm. Note that when sorting linked lists, merge sort requires only Θ(log(n)) extra space (for recursion).

Merge sort is the algorithm of choice for a variety of situations: when stability is required, when sorting linked lists, and when random access is much more expensive than sequential access (for example, external sorting on tape).

There do exist linear time in-place merge algorithms for the last step of the algorithm, but they are both expensive and complex. The complexity is justified for applications such as external sorting when Θ(n) extra space is not available.

core concept 核心概念

  • MergeSort is a divide and conquer algorithm 分而治之的思想
  • 空间换时间,并且 stable,保持稳定性这一点是它的亮点
  • 二分思想

concrete step 具体步骤

  1. 把长度为 n 的输入序列分成两个长度为 n / 2 的子序列;
  2. 对这两个子序列分别采用 Merge Sort;
  3. 将两个排序好的子序列合并成一个最终的排序序列。

basic code 基本实现

以迭代的方式来实现(但要注意防止函数调用过深导致 JavaScript 的运行栈溢出):

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 mergeSort(arr) {  // recursion
var len = arr.length;
var mid = Math.floor(len / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);

if (len < 2) {
return arr;
}

return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
var result = [];

while (left.length > 0 && right.length > 0) { // sorting: small to big
result.push(left[0] <= right[0] ? left.shift() : right.shift()); // keep stable
}

return result.concat(left, right);
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

Heap Sort 堆排序

heap 堆的定义

二叉堆是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是大于或等于任何一个子节点的键,且每个节点的左子树和右子树都是一个二叉堆。 当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

concise explanation 简明解释

堆排序可以认为是选择排序的改进版,像选择排序一样将输入划分为已排序和待排序,不一样的是堆排序利用堆这种近似完全二叉树的良好的数据结构来实现排序,本质上使用了二分的思想。先将所有的数据堆化,然后移动 arr[0] 到数组末尾(已排序区域),再重新堆化,依次这样循环来排序。

利用堆这种良好的数据结构,它在拥有良好的可预测性的同时(不管输入什么都是 O(n·log(n)) time ),但它的缺点也有:即不稳定,而且 O(n·log(n) 的平均效率决定了它的效率不如快速排序。适用于数据库内引擎排序(需要这样的可预测性性能)。

properties 特性

  • Not stable
  • Not really adaptive
  • O(n·log(n)) time
  • O(1) extra space

core concept 核心概念

  • 利用良好的数据结构——堆,来排序
  • 二分的思想
  • 选择排序的改进版,继承了”可预测性”(什么数据输入都为 O(n·log(n) time)

concrete step 具体步骤

  1. 将初始待排序关键字序列 (R1,R2….Rn) 构建成大顶堆(堆本身的概念见维基解释),此堆为初始的无序区;
  2. 将堆顶元素 R[1] 与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1) 和新的有序区 (Rn) ,且满足 R[1,2…n-1] <= R[n];
  3. 由于交换后新的堆顶 R[1] 可能违反堆的性质,因此需要对当前无序区 (R1,R2,……Rn-1) 调整为新堆,然后再次将 R[1] 与无序区最后一个元素交换,得到新的无序区 (R1,R2….Rn-2) 和 新的有序区 (Rn-1,Rn) 。不断重复此过程直到有序区的元素个数为 n-1 ,则整个排序过程完成。

basic code 基本实现

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
function heapSort(arr) {
var i;
var size = arr.length;

// 初始化 heap,i 从最后一个父节点开始调整,直到节点均调整完毕 (https://en.wikipedia.org/wiki/Heapsort#Overview)
for (i = Math.floor(size / 2) - 1; i >= 0; i--) {
heapify(arr, i, size);
}
// 堆排序:先将第一个元素和已拍好元素前一位作交换,再重新调整,直到排序完毕
for (i = size - 1; i > 0; i--) {
swap(arr, 0, i);
size -= 1;
heapify(arr, 0, size);
}

return arr;
}

function heapify(arr, index, size) {
var largest = index;
var left = 2 * index + 1; // https://en.wikipedia.org/wiki/Heapsort#Overview
var right = 2 * index + 2;

if (left < size && arr[left] > arr[largest]) {
largest = left;
}
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== index) {
swap(arr, index, largest);
heapify(arr, largest, size);
}
}

// test
var arr = [91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22];
console.log(heapSort(arr));
// [10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

wikipedia solution 维基上给出的另一个方法

wikipedia 上给出的方法于 basic code 基本实现的区别在于维护堆性质时采用的方式不同,本质是一样的:

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
function heapSort(arr) {
var i;
var size = arr.length;

// 初始化 heap,i 从最后一个父节点开始调整,直到节点均调整完毕 (https://en.wikipedia.org/wiki/Heapsort#Overview)
for (i = Math.floor(size / 2) - 1; i >= 0; i--) {
heapify(i, size);
}
// 堆排序:先将第一个元素和已拍好元素前一位作交换,再重新调整,直到排序完毕
for (i = size - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(0, i);
}

return arr;
}

function heapify(start, end) {
// 建立父节点下标和子节点下标
var dad = start;
var son = dad * 2 + 1;

if (son >= end) {
return 0;
}
if (son + 1 < end && arr[son] < arr[son + 1]) {
son++;
}
if (arr[dad] <= arr[son]) {
swap(arr, dad, son);
heapify(son, end);
}

return 0;
}

// test
var arr = [91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22];
console.log(heapSort(arr));
// [10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

Quick Sort 快速排序

concise explanation 简明解释

  1. 从数列中挑出一个元素,称为”基准”(pivot),
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

properties 特性

  • Not stable
  • Not adaptive
  • O(n²) time, but typically O(n·log(n)) time (or more faster)
  • O(log(n)) extra space (see discussion)

When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort

core concept 核心概念

  • divide and conquer algorithm. (使用了分而治之的思想)

concrete step 具体步骤

  1. 从数列中挑出一个元素,称为”基准”(pivot),
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

basic code 基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr) {
var i;
var pivot = arr[0]; // or some other pivot, just for understand easily
var left = [];
var right = [];
var len = arr.length;

if (len < 2) {
return arr;
}
for (i = 1; i < len; i++) {
arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
}

return quickSort(left).concat([pivot], quickSort(right));
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));

use array.forEach(), functional programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort(arr) {
var pivot = arr.splice(0, 1)[0]; // or some other pivot, just for understand easily
var left = [];
var right = [];
var len = arr.length;

if (len < 2) {
return arr;
}
arr.forEach(function sort(element) {
element <= pivot ? left.push(element) : right.push(element);
});

return quickSort(left).concat([pivot], quickSort(right));
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));

middle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function quickSort(arr) {
var i;
var left = [];
var right = [];
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var len = arr.length;

if (len < 2) {
return arr;
}
for (i = 0; i < len; i++) {
arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
}

return quickSort(left).concat([pivot], quickSort(right));
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

use array.forEach(), functional programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr) {
var left = [];
var right = [];
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var len = arr.length;

if (len < 2) {
return arr;
}
arr.forEach(function sort(element) {
element <= pivot ? left.push(element) : right.push(element);
});

return quickSort(left).concat([pivot], quickSort(right));
}

// test
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

in-place

上面简单版本的缺点是,它需要Ω(n)的额外存储空间,也就跟归并排序一样不好。额外需要的内存空间配置,在实际上的实现,也会极度影响速度和缓存的性能。有一个比较复杂使用原地(in-place)分区算法的版本,且在好的基准选择上,平均可以达到O(log n)空间的使用复杂度。

1
2


Summary 总结

compare 比较

好了,现在终于到了各个算法大 PK 的时候了:

数据几乎快排序完成时?

插入排序不解释

数据量小,对效率要求不高,代码简单时?

性能大小:希尔排序 > 插入排序 > 冒泡排序 > 选择排序

数据量大,要求稳定的效率(不会像快速排序一样有 O(n²) 的情况)(如数据库中)?

堆排序

数据量大,要求最好的平均效率?

性能大小: 快速排序 > 堆排序 > 归并排序

因为虽然堆排序做到了 O(n·log(n) time,而快速排序的最差情况是 O(n²),但是快速排序的绝大部分时间的效率比 O(n·log(n) 还要快,所以快速排序真的无愧于它的名字。(十分快速)

真正的总结

正如开头所说,世界上没有最好的算法(《人月神话》:没有银弹),只有最适合某种情况的算法。

算法代有人才出,各领风骚数十载。领悟经典算法其中的精髓才是王道:

缓存位置、双向遍历、二分、分而治之、利用良好的数据结构、利用高深的数学技巧…这些算法背后的思想所带给我们的远比代码本身更有价值

最后引用 + 改编一下陈立杰的话:

现在是计算机科学的黄金时代,也是全人类的黄金时代,能够站在这样的黄金时代里,我感到无比的荣幸,我们都梦想能够成为黄金时代大潮中的一朵浪花,为人类智慧添砖加瓦。

加瓦把骚年~

Reference & Thanks 引用 & 感谢

文章标题:优雅的 JavaScript 排序算法(Old Edition)

文章作者:RayJune

时间地点:晚上10:27,于桂苑5寝室

原始链接:https://www.rayjune.me/2017/10/19/elegant-JavaScript-sorting-algorithm/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。