js线性排序算法

发表于 | 分类于 | 阅读次数:

最近准备学习一下算法的一些知识，这里做一下笔记。

我们经常耳熟能详的一些算法，例如快排，归并，堆排序等，都是用比较的操作来进行排序的，这几种排序方法都可以达到上界 O(n log n)。

现在我们来了解一些不常用的线性排序算法，这些算法时间复杂度可以达到 O(log n)，不过都是在牺牲空间换取时间，一般来说我们基本不会用到这几种算法，只是给我们开阔一下思维方式。

计数排序

基础思想

计数排序的基本思想就是，对数组中每一个元素 x，确定出小于 x 的个数，然后我们就可以根据这一信息得到每一个元素在数组排列的位置。

时间复杂度：O(n); 空间复杂度：O(n+k)

步骤

例如给定数组

1
2

var arr = [6,4,5,6,3,7,4]

第一步：

通过一次循环得到数组中最大的数为 7，然后初始化一个用于记录的数组，他的数组长度和 arr 的最大的数一样大，
最后得到的数组将会是

1
2

var record_arr = [0,0,0,0,0,0,0]; // 数组大小为7

第二步：

遍历 arr，用record_arr记录每个数字出现的次数

1
2
3
4

for (var i = 0 ; i < arr.length; i ++;) {
    record_arr[arr[i]] ++;
}

第三步：

按顺序遍历出 record_arr ，这里有两种做法，我们先来看一下比较简单粗暴的方法。

1
2
3
4
5
6
7
8
9
10

var result = [];

for (var i = 0 ; i < record_arr.length; i ++;) {
    if (record_arr[i] > 0) {
        for (var j = 0; j < record_arr[i]; j++) {
            result.push(i);
        }
    }
}

网上给的基本都是这种方法，思维方式可能会比较绕一点

1
2
3
4
5
6
7
8
9

for (var i = 1 ; i < record_arr.length; i++;) {
    record_arr[i] += record_arr[i-1]; // 这样我们就可以知道每个位置的元素，前面有多少个元素了，然后就可以通过前面元素的数量推断出挡墙这个元素所处的位置
}
var result = [];
for (var i = arr.length - 1; i >=0; i-- ) {
    result[record_arr[arr[i]] - 1] = arr[i]; // 通过元素前的数量将元素插入到指定的位置
    record_arr[arr[i]]--;
}

两个方法效率都一样，只是思维的方式不同，可以都尝试理解一下。

最后整合代码之后是这样的：

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 count_sort(arr) {
    var max_value;
    var result = [];

    max_value = arr.reduce((accumulator, current) => { return accumulator > current ? accumulator : current; })

    var record_arr = (new Array(max_value + 1)).fill(0);

    arr.forEach((value) => {
        record_arr[value] ++;
    })

    for (var i = 1 ; i < record_arr.length; i++) {
        record_arr[i] += record_arr[i-1];
    }


    var result = [];
    for (var i = arr.length - 1; i >=0; i-- ) {
        result[record_arr[arr[i]] - 1] = arr[i];
        record_arr[arr[i]]--;
    }
    return result;
}

此算法的缺陷也非常明显，根据待排数组中最大值，可能会导致大量无用的内存占用，而且无法对负数和小数进行排序，所以基本上根本看不到会有使用这个算法的地方，但是算法思想还是可以借鉴的。

基数排序

基础思想

从个位到十分位，再到百分位，依次进行排序，每次排序必须采用时间稳定的算法，可以采用上面的计数排序。

时间复杂度：O(n); 空间复杂度：O(n+k)

步骤

第一步：

给定一个数组

1
2

var arr = [23,40,12,145];

先将个位排序

1
arr = [40,12,23,145];

再排十位

1
arr = [12,23,40,145];

最后排百位

1
arr = [12,23,40,145];

桶排序

基础思想

将区间[0,1)分成n个相同大小的子区间，或称为桶。然后将n个输入元素分布到各个桶中去。每个桶中的元素用一个链表来存储。先对每个桶中的数据进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。

桶排序假设输入数据服从均匀分布，因此每个桶中的数据量相差不多，平均情况下它的时间代价为O(n)。

时间复杂度是O(n)。空间复杂度是O(n)。需要一个辅助数组来存放桶（链表）。