学习

常见排序算法（一）

刚刚经历了秋招，在各大公司的笔试算法题中被虐的惨不忍睹。以前做前端，更多的注重html, css页面部分，以及js的交互处理，网络请求，对算法使用不多。最近刚好有时间，复习一下常用的算法和时间，空间复杂度的计算，也为明年的春招做准备吧。

本节中主要这些排序算法：

1. 选择排序及其优化
2. 冒泡排序及其优化
3. 插入排序及其优化
4. 希尔排序及其优化

本文的排序都是从小到大排序，反序的话也很容易搞，就不多说了。

选择排序及其优化

选择排序，每次把参与排序的数组元素中最小值放在参与排序的元素的最前面。每次进行比较时，初始化最小值的索引为参与排序的元素的起始元素的索引，然后起始元素与其它元素进行比较，如果有元素小于最小值索引对应的值，就改变最小值索引为该元素的索引。最后，交换最小值索引对应的值和起始值，确定出上一轮排序的最小值，并放在前面。以此类推进行排序。
如图所示：

下面用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
function selectionSort(arr) {
    let len = arr.length,
        minValue, minIndex;

    if (arr.length <= 1) {
        return arr;
    }

    for (let i = 0; i < len - 1; i ++ ) {
        minIndex = i;

        for (let j = i + 1; j < len; j ++ ) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }

        // 如果有其它元素小于初始元素，交换位置
        if (minIndex !== i) {
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
    }
}

// test
let arr = [ 0, 0, 1, 9, 6, 1, 2, 5, 5, 6 ];
selectionSort(arr);
console.log(arr); // [ 0, 0, 1, 1, 2, 5, 5, 6, 6, 9 ]

当minIndex !== i时，也就是最小值索引不是起始值索引时，交换起始值和最小值。这步相对来说算是一个小优化，避免了可能的无意义的交换。

选择排序属于原地排序，时间复杂度为O(n^2);

冒泡排序及其优化

冒泡排序，每次从第一个元素开始，与其它元素两两比较，当前元素大于后一个元素，两者交换，直到把最大的数放在数组的最后，下次比较最大元素之前的元素，再把第二大的元素放在最大元素之前，以此类推，直到第一个元素，整个排序就完成了。

第一版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len; i ++ ) {

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

// 测试
let arr = [ 2, 8, 4, 0, 2, 7, 1, 0, 9, 6 ];
bubbleSort(arr);
console.log(arr); // [ 0, 0, 1, 2, 2, 4, 6, 7, 8, 9 ]

冒泡排序第一版完成了，排序效果大体看来还行，能正确地排序了。这是我之前的想法，接触了算法以后，冒泡算法应该不止于此，应该有可优化的空间。
在第一版的冒泡排序中，假设数组有n个元素，外围的循环要进行n次，里面的循环依次要进行n-1,n-2,n-3,……,1次。内层每次循环，都要进行两两比较，对于一般的无序数组，排序足够用了。
然而，当数组是[1, 4, 3, 6, 7, 8, 9]的时候呢，从第四项到第七项，数组已经是有序的，但是按照第一版的来看，即使是有序的部分，依然需要进行循环和两两比较。仔细想一想，有没有什么办法跳过这些无意义的过程呢？

我们可以这样看：每次开始比较前，我们设置一个标志位：flag = 0。当里面的循环发生交换了，flag就变为1，否则，就表示后边的元素都比前一个元素小，也就是后边的部分已经是有序的了。当一次内层循环完成时，在外围循环中判断flag，如果flag为0，表示这次循环没有发生交换，即后边的每一个数都比前一个数大，此时就没有必要继续比较，要提前退出循环，避免了无意义的比较。
下面我们来实现第二版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function bubbleSort2(arr) {
  let len = arr.length，flat = 0;

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

    if (flag === 0) {
      break;
    }
  }
}

// 测试
let arr = [1, 4, 3, 6, 7, 8, 9];
bubbleSort2(arr);
console.log(arr); // [1, 3, 4, 6, 7, 8, 9]

至于说第二版有多大的性能提升，等下一个优化版本出来的时候一起测试；第二版避免了一部分的无意义的循环和比较，理论上能够提升性能。
然而，如果是[1, 2, 4, 3, 2, 5, 5, 6, 7]时，采用第二版的优化，可以不用比较从第六项以后的部分，但是这里还存在优化空间。对于前五项，每一次比较时，都要与最后边的5,5,6,7这些进行比较，但这些比较很显然也是多余的。这时候呢，内层循环部分还可以继续优化。接下来我们进行第三版的优化。
我们用一个标志做lastSwapWord来标记最后一次交换发生的位置。比如，在1和其它值进行比较时，我们到达第一个5时，发生了这次比较的最后一次交换，这代表5后边的数都比前五个元素要大，因此下一次进行比较时，就不用比较5后面的数了，此时设置lastSwapWord等于第一个5所在的位置，下一次进行比较时，只需要比较到lastSwapWord就可以了。再配上第二步的优化，可以提前结束循环。
下面是第三版的代码：

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
function bubbleSort3(arr) {
  let len = arr.length, flag = 0, lastSwapWord = 0, k = len - 1;

  for (let i = 0; i < len; i ++ ) {
    flag = 0;
    for (let j = 0; j < k ; j ++ ) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = 1;
        lastSwapWord = j;
      }
    }

    k = lastSwapWord;
    if (flag === 0) {
      break;
    }
  }
}

// 测试
let n = 10;
let arr = [1, 2, 4, 3, 2, 5, 5, 6, 7];
bubbleSort3(arr);
console.log(arr); // [ 1, 2, 2, 3, 4, 5, 5, 6, 7 ]

下面来测试一下三个版本的冒泡排序在时间上的差异。

1
2
3
4
5
6
7
8
9
10
11
12
13
let utils = require('./../utils');
let n = 20000;
let arr = utils.getRandomArray(n, 0, n); // 生成随机数数组
let arr2 = utils.copyArray(arr);
let arr3 = utils.copyArray(arr);

let time1 = utils.testSort(arr, bubbleSort);
let time2 = utils.testSort(arr2, bubbleSort2);
let time3 = utils.testSort(arr3, bubbleSort3);

console.log('bubble  sort: ', time1); // bubble  sort:  2.522000 s
console.log('bubble sort2: ', time2); // bubble sort2:  2.479000 s
console.log('bubble sort3: ', time3); // bubble sort3:  2.436000 s

当采用系统随机生成的数字数组进行测试时，结果如上。结合多次实验可以看到：bubbleSort3用时最少，bubbleSort2用时其次，bubbleSort的用时最长。

下面测试一下近乎排序好的数组用冒泡排序进行排序的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 测试
let utils = require('./../utils');
let n = 50000;
let arr = utils.getNearlyArray(n, 1); // 生成一个函数，[1,2,3,4,5...49999],随意将其中的两个数进行交换
let arr2 = utils.copyArray(arr);
let arr3 = utils.copyArray(arr);

let time1 = utils.testSort(arr, bubbleSort);
let time2 = utils.testSort(arr2, bubbleSort2);
let time3 = utils.testSort(arr3, bubbleSort3);

console.log('bubble  sort: ', time1); // bubble  sort:  5.000000 s
console.log('bubble sort2: ', time2); // bubble sort2:  2.673000 s
console.log('bubble sort3: ', time3); // bubble sort3:  2.497000 s

在对近乎有序的数组进行排序时，可以看到第二版和第三版带来的巨大的性能提升。
不过之前测试的时候使用的是c++，同样的数据量，速度比js要快得多。

插入排序及其优化

讲完冒泡排序，接下来讲一下插入排序。插入排序是从数组的第二个元素开始，与它前面部分的值进行比较，如果小于前面的值，就在比较值前插入元素（也可以说交换两个元素的位置）；到了第三个元素，与第二个元素进行比较，如果小于第二个元素，交换位置，比较第二个和第一个元素；以此类推，直到最后。
如图所示：

下面我们来实现第一版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 插入排序
const insertSort = arr => {
  let len = arr.length, index;

  for (let i = 1; i < len; i ++ ) {
    index = i;

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

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

第一版的排序算法大致就是这样，能够进行基本的排序。但是它有没有改进的余地呢？肯定是有的。在while循环中，如果arr[index] < arr[index - 1]就需要进行一次交换，而计算机进行数组交换相较于赋值来说是一个耗时耗费资源的操作，能不能用赋值来减少交换的次数呢？肯定是可以的。
下面来看看我们的第二版优化版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const insertSort2 = arr => {
  let len = arr.length, index, val;

  for (let i = 1; i < len; i ++ ) {
    index = i;
    val = arr[i];
    while(index > 0 && val < arr[index - 1]) {
      arr[index] = arr[index - 1];
      index--;
    }

    if (index !== i) {
      arr[index] = val;
    }
  }
}

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

下面比较一下两种插入排序算法的时间上的差别。
先看一下排序一个近乎有序的数组：

1
2
3
4
5
6
7
8
9
10
let utils = require('./../utils');
let n = 20000000;
let arr = utils.getNearlyArray(n, 1); // 一个近乎有序的数组
let arr2 = utils.copyArray(arr);

let time1 = utils.testSort(arr, insertSort);
let time2 = utils.testSort(arr2, insertSort2);

console.log('insert  sort: ', time1); // insert  sort:  0.700000 s
console.log('insert sort2: ', time2); // insert sort2:  0.213000 s

再看一下无序数组的排序情况：

1
2
3
4
5
6
7
8
9
10
let utils = require('./../utils');
let n = 50000;
let arr = utils.getRandomArray(n, 1); // 一个无序的数组
let arr2 = utils.copyArray(arr);

let time1 = utils.testSort(arr, insertSort);
let time2 = utils.testSort(arr2, insertSort2);

console.log('insert  sort: ', time1); // insert  sort:  14.545000 s
console.log('insert sort2: ', time2); // insert sort2:  0.911000 s

这个差别就很明显了，优化后的版本的所用时间远少于第一版。性能上提升明显。数据量越大，差别就越明显。同时也说明，数组中的数据交换相对于赋值来说真的费时间。

希尔排序

希尔排序，其实可以看作是插入排序的另一个优化版本。不同之处在于插入排序默认的间隔为1，相邻元素两两直接比较；而希尔排序的间隔不为1，初始值一般为数组长度除以2，当然，也可以选择其它合适的间隔。初始间隔为gap = len / 2(可以不是2), 然后每次除以2或其它值，直到间隔为1；在每一个间隔上，进行插入排序。通过缩小间隔，到间隔为1时，基本上比较小的数在前，比较大的数排在后边，数组近乎一个有序数组，最后进行微调就可以了。
如图所示：

下面来看下算法实现：

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 shellSort = arr => {
  let len = arr.length,
      index, val, gap;

  for (gap = Math.floor(len / 2); gap >= 1; gap = Math.floor(gap /= 2)) {
    for (let j = gap; j < len; j ++ ) {
      index = j;
      val = arr[index];
      while((index - gap) >= 0 && val < arr[index - gap]) {
        arr[index] = arr[index - gap];
        index -= gap;
      }
      if (index !== j) {
        arr[index] = val;        
      }
    }
  }
}

let utils = require('./../utils');
let n = 10;
let arr = utils.getRandomArray(n, 0, n);
console.log(arr); // [ 2, 5, 3, 7, 0, 2, 8, 6, 6, 7 ]
shellSort(arr);
console.log(arr); // [ 0, 2, 2, 3, 5, 6, 6, 7, 7, 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
30
let utils = require('./../utils');
let Insert = require('./insertSort');
let Bubble = require('./bubble');
let Select = require('./selectionSort');
let Shell = require('./shellSort');

let n = 80000;
// let arr = utils.getRandomArray(n, 0, n);
let arr = utils.getNearlyArray(n, 1); // 近乎有序的数组
let arr2 = utils.copyArray(arr);
let arr3 = utils.copyArray(arr);
let arr4 = utils.copyArray(arr);

let time1 = utils.testSort(arr, Bubble.bubbleSort3);
let time2 = utils.testSort(arr2, Insert.insertSort2);
let time3 = utils.testSort(arr3, Select.selectionSort);
let time4 = utils.testSort(arr4, Shell.shellSort);

// 当排序近乎有序的数组时，80000的数据量
console.log('bubble sort: ', time1); // bubble  sort:  2.604000 s
console.log('insert sort: ', time2); // insert sort:  0.002000 s
console.log('select sort: ', time3); // select sort:  10.727000 s
console.log('shell  sort: ', time4); // shell sort:  0.039000 s

// 当排序随机无序的数组时，依旧是80000的数据量
console.log('bubble sort: ', time1); // bubble  sort:  42.850000 s
console.log('insert sort: ', time2); // insert sort:  1.998000 s
console.log('select sort: ', time3); // select sort:  11.893000 s
console.log('shell  sort: ', time4); // shell sort:  0.107000 s

由此可见，无论是排有序数组还是无序数组，希尔排序和插入排序的性能都更优一些。在排序无序数组时，冒泡排序的的性能不如选择排序；而在排序有序数组时，选择排序的性能不如冒泡排序。
那么，在数组中元素个数多，数组元素的范围小的时候，很有可能出现相当一部分已经排好的序列。此时，用插入排序或者希尔排序是更优选择。

本次讲解了冒泡排序，希尔排序，选择排序，插入排序及其优化，在大数据发展的今天，选择合适的算法处理数据，具有重要意义。
下节将重点介绍归并排序，堆排序，快速排序及其优化，希望对自己和大家有所帮助。