学习

常见排序算法（2）

本文主要讲一下复杂度为O(nlogn)的算法及其优化。

1. 归并排序及其优化
2. 快速排序及其优化
3. 堆排序及其优化

归并排序及其优化

归并排序，简而言之就是先拆分再合并。把数组从中间不断地拆分，最后成为单个元素，然后元素相邻两两比较，合并成数组，然后相邻数组比较，继续合并，依次类推，直到数组合并完成。
如图所示：

下面用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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function _mergeSort(arr, l, r) {
  // 当数组被拆的只剩下一个元素，就返回
  if (l >= r) {
    return;
  }

  let mid = Math.floor((l + r) / 2);
  _mergeSort(arr, l, mid);
  _mergeSort(arr, mid + 1, r);
  _merge(arr, l, mid, r);
}

function _merge(arr, l, mid, r) {
  let temp = [];
  for (let i = 0; i < r - l + 1; i ++) {
    temp[i] = arr[i + l];
  }

  let i = l, j = mid + 1;
  for (let k = l; k <= r; k ++ ) {
    if (j > r) {
      arr[k] = temp[i - l];
      i ++;
    } else if (i > mid) {
      arr[k] = temp[j - l];
      j ++;
    } else if (temp[i - l] > temp[j - l]) {
      arr[k] = temp[j - l];
      j ++;
    } else {
      arr[k] = temp[i - l];
      i ++;
    }
  }
}

const mergeSort = arr => {
  let n = arr.length;

  _mergeSort(arr, 0, n - 1);
}

let utils = require('./../utils');
let n = 10;
let arr = utils.getRandomArray(n, 0, n);
console.log(arr); // [ 2, 8, 0, 1, 3, 5, 5, 3, 6, 0 ]
mergeSort(arr);
console.log(arr); // [ 0, 0, 1, 2, 3, 3, 5, 5, 6, 8 ]

第一版归并排序就是这样，当然，它也有可以优化的空间。

1
2
3
4
5
6
7
8
9
10
11
// 在这里测试一下归并排序和插入排序的性能
let utils = require('./../utils');
let Insert = require('./insertSort');
let n = 500;
let arr = utils.getRandomArray(n, 0, n);
let arr2 = utils.copyArray(arr);
let time1 = utils.testSort(arr, mergeSort);
let time2 = utils.testSort(arr2, Insert.insertSort2);

console.log('merge sort: ', time1);
console.log('insert sort: ', time2);

经过多次测试发现，在数据量小于一定数值（我这里时500）时，插入排序的效率要比归并排序高。所以在_mergeSort中，对于数据量小于20（也可以为其它合适的值，这里暂定为20），我们使用插入排序代替归并排序，在这里要对插入排序做一下调整。

1
2
3
4
5
6
7
8
9
10
11
12
const insertSort = (arr, l, r) => {
  for (let i = l; i <= r; i ++) {
    let val = arr[i],
        index = i;

    while(index > 0 && val < arr[index - 1]) {
      arr[index] = arr[index - 1];
      index--;
    }
    arr[index] = val;
  }
}

同时呢，我发现，在_mergeSort中，并不是每次都需要调用_merge函数的。凡是进入到merge中的数组，各自都是有序的，也就是说arr[l, mid]和arr[mid+1, r]是有序的。如果arr[mid] < arr[mid+1]，那么就意味着arr[l, mid]部分的数整体小于arr[mid+1, r]，此时再进入合并没有意义，在这块儿也做下判断，避免不必要的合并。
下面是第二版的归并排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const _mergeSort2 = (arr, l, r) => {
  if (l >= r) {
    return;
  }

  if (r - l <= 20) {
    insertSort(arr, l, r);
    return;
  }

  let mid = Math.floor((l + r) / 2);
  _mergeSort2(arr, l, mid);
  _mergeSort2(arr, mid + 1, r);
  if (arr[mid] > arr[mid + 1]) {
    _merge(arr, l, mid, r);
  }
}
const mergeSort2 = arr => {
  let n = arr.length;
  _mergeSort2(arr, 0, n - 1);
}

它的性能测试我们稍后进行。第二版对小数组的排序和合并进行了优化。下面我们考虑一下如何对既有的算法进一步优化。归并是先对数组进行拆分，然后排序，再一步步合并合并。能不能直接开始排序，然后合并，省去递归拆分的过程。接下来我按照这个思路写下第三版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const mergeSort3 = arr => {
  let n = arr.length;
  if (n < 20) {
    insertSort(arr, 0, n - 1);
    return;
  }

  for (let size = 1; size <= n; size *= 2) {
    for (let j = 0; j + size - 1 < n; j *= size * 2) {
      if (arr[j + size - 1] > arr[j + size]) {
        _merge(arr, j, j + size - 1, Math.min(j + size * 2 - 1, n - 1));
      }
    }
  }
}

下面来测试一下这三版的性能：

1
2
3
4
5
6
7
8
9
10
11
let utils = require('./../utils');
let n = 2000000;
let arr = utils.getRandomArray(n, 0, n);
let arr2 = utils.copyArray(arr);
let arr3 = utils.copyArray(arr);
let time1 = utils.testSort(arr, mergeSort);
let time2 = utils.testSort(arr2, mergeSort2);
let time3 = utils.testSort(arr3, mergeSort3);
console.log('merge sort: ', time1);   
console.log('merge sort2: ', time2);
console.log('merge sort3: ', time3);

从多次测试结果来看，第二版和第三版的运行速度快于第一版，但是在速度提升不明显，不太稳定。

快速排序及优化

快速排序，每次在数组中选出一个数作为基准，对数组进行排序，大于基准数的放在基准数的右边，小于基准数的放基准数的左边；然后对基准数左边和右边的部分各自再选一个数做基准数，重复之前的步骤，以此类推，直到最后数组被完全排序。
如图所示：

下面用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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 快速排序
const _partion = (arr, l, r) => {
  let randIndex = Math.floor(Math.random() * (r - l + 1)) + l;
  [arr[randIndex], arr[l]] = [arr[l], arr[randIndex]];
  let i = l + 1, j = r, val = arr[l];
  while(true) {
    while(i <= r && arr[i] < val) {
      i ++;
    }
    while(r >= l + 1 && arr[j] > val) {
      j --;
    }
    if (i > j) {
      break;
    }

    [arr[i], arr[j]] = [arr[j], arr[i]];
    i ++;
    j --;
  }

  [arr[j], arr[l]] = [arr[l], arr[j]];
  return j;
}

const _quickSort = (arr, l, r) => {
  if (l >= r) {
    return;
  }

  let index = _partion(arr, l, r);
  _quickSort(arr, l, index - 1);
  _quickSort(arr, index + 1, r);
}

const quickSort = arr => {
  let n = arr.length;
  _quickSort(arr, 0, n - 1);
}

let utils = require('./../utils');
let n = 10;
let arr = utils.getRandomArray(n, 0, n);
console.log(arr); // [ 1, 4, 5, 5, 4, 0, 8, 6, 7, 0 ]
quickSort(arr);
console.log(arr); // [ 0, 0, 1, 4, 4, 5, 5, 6, 7, 8 ]

在这里，我们实现了第一版的快速排序。那么他能够在哪里进行优化呢？在_partion中，对于等于基准数的数，我们都让它尽可能平均分布于左右两侧。那么如果我们做下标记直接把等于基准数的部分都排在一起，那么下次我们就可以只排小于基准数的部分和大于基准数的部分，能够减少排序的总次数，也可以理解为将整个数组分为三部分，大于基准数，小于基准数和等于基准数的。下次排序时，只排序大于和小于基准数的部分。
下面我们来做下第二版的快速排序的实现。

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
const _quickSort2 = (arr, l, r) => {
  if (l >= r) {
    return;
  }

  let randIndex = Math.floor(Math.random() * (r - l + 1)) + l;
  [arr[randIndex], arr[l]] = [arr[l], arr[randIndex]];
  let lt = l,
      gt = r + 1,
      i = lt + 1,
      val = arr[l];

  while(i < gt) {
    if (arr[i] > val) {
      [arr[i], arr[gt - 1]] = [arr[gt - 1], arr[i]];
      gt --;
    } else if (arr[i] < val) {
      [arr[i], arr[lt + 1]] = [arr[lt + 1], arr[i]];
      i ++;
      lt ++;
    } else {
      i ++;
    }
  }

  [arr[l], arr[lt]] = [arr[lt], arr[l]];
  _quickSort2(arr, l, lt - 1);
  _quickSort2(arr, gt, r);
}

const quickSort2 = arr => {
  let n = arr.length;
  _quickSort2(arr, 0, n - 1);
}

下面我们来测试一下两个版本的性能。

1
2
3
4
5
6
7
8
9
10
11
let utils = require('./../utils');
let n = 100000;
let arr = utils.getRandomArray(n, 0, n);
// let arr = utils.getNearlyArray(n, 1);
let arr2 = utils.getRandomArray(n, 0, n);

let time1 = utils.testSort(arr, quickSort);
let time2 = utils.testSort(arr2, quickSort2);

console.log('quick sort1: ', time1); // quick sort1:  0.067000 s
console.log('quick sort2: ', time2); // quick sort2:  0.112000 s

然而，在实际地测试中，第二版的性能并没有第一版的优。至于选哪个，大家酌情选择吧。

堆排序

堆排序，利用堆积树进行排序。最大堆，就是根结点要大于两个子节点的值。下面我们先来实现下堆的数据结构。

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
const __shiftDown = (arr, n, j) => {
  while(j * 2 + 1 < n) {
    let k = j * 2 + 1;
    if (k + 1 < n && arr[k + 1] > arr[k]) {
      k += 1;
    }

    if (arr[j] > arr[k]) {
      break;
    }

    [arr[j], arr[k]] = [arr[k], arr[j]];
    j = k;
  }
}
const heapSort = arr => {
  let n = arr.length;
  for (let i = Math.floor(n / 2); i >= 0; i --) {
    __shiftDown(arr, n, i);
  }

  for (let j = n - 1; j > 0; j --) {
    [arr[0], arr[j]] = [arr[j], arr[0]];
    __shiftDown(arr, j, 0);
  }
}

堆排序大概就是这样。第一个for循环过后，会形成最大堆，即根结点要比每一个子节点都大；第二个for循环，先把最大的根结点的值和数组中最后一个值互换，然后排序从第1个到第n-1个值。每次都会确定一个最大的值放在合适的位置，直到根结点。

最后以一张各种排序算法复杂度总表来结束本篇文章。