数据结构与算法系列

数据结构与算法系列(8)--非比较排序

前面的排序都是基于比较进行的排序，而基于比较进行排序的效率最快也只是nlogn,而在某些情况下可以不需要比较就进行排序，从而达到一个极好的效率，这里主要介绍计数排序、基数排序、以及桶排序

计数排序

计数排序主要针对正整数数组，通过查询数组中的最大值和最小值，来设置存储数据的计数数组的大小，然后遍历将整数n对应的arr[n]的值加一，最后遍历计数数组，将存储的内容返回

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 CountSort(arr){
    let min = Infinity
    let max = 0
    let len = arr.length
    for (let i = 0; i < len; i++){
        if (arr[i] < min) min = arr[i]
        if (arr[i] > max) max = arr[i]
    }

    let countarr = new Array(max - min + 1).fill(0)

    for (let i = 0; i < len; i++){
        countarr[arr[i] - min]++
    }

    let p = 0
    for (let i = 0; i <= max - min; i++){
        for (let j = 0; j < countarr[i]; j++){
            arr[p] = i + min
            p++
        }
    }

    return arr
}

算法属性

最优时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
Ω(n+k) Θ(n+k) O(n+k) O(k) 稳定

这里的k就是待排序数组里面的最大值减去最小值，计数排序在面对最小值和最大值之差的数值远大于原数组数据量的时候，效率反而会很差

基数排序

为了解决计数排序的缺陷，通过基数进行排序的算法也就出来了，它类似于计数排序，但是是基于基数来进行的

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
function BaseSort(arr){
    let len = arr.length

    let max = 0
    for (let i = 0; i < len; i++){
        if (arr[i] > max) max = arr[i]
    }

    let x = 1
    while (true){
        let baseArr = new Array(10).fill(0).map(_ => new Array())

        for (let i = 0; i < len; i++){
            let j = parseInt(arr[i] / x) % 10
            baseArr[j].push(arr[i])
        }

        let p = 0
        baseArr.forEach(base => {
            base.forEach(data => {
                arr[p] = data
                p++
            })
        })

        x = x * 10
        if (x > max) break
    }

    return arr
}

算法属性

最优时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
Ω(n*q) Θ(n*q) O(n*q) O(n+k) 稳定

基数排序中k是桶的个数，在这里就是基数排序时，数值的进制，而q表示的最大的位数。在网上大都都是将q和k认为是同一值，但是从算法可以明显看出来，空间复杂度和时间复杂度，依靠的内容不同

桶排序

桶排序也是对计数排序的优化，计数排序吧每个数值都展开了，导致会消耗大量的空间，而桶排序这是将这些数值划分为一个个的区间段

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
function BucketSort(arr, bukectSize = 10){
    let min = Infinity
    let max = 0
    let len = arr.length
    for (let i = 0; i < len; i++){
        if (arr[i] < min) min = arr[i]
        if (arr[i] > max) max = arr[i]
    }

    let bucketNum = parseInt((max - min) / bukectSize) + 1
    let buckets = new Array(bucketNum).fill(0).map(_ => new Array())

    for (let i = 0; i < len; i++){
        let b = parseInt((arr[i] - min) / bukectSize)
        let bucket = buckets[b]
        let len = bucket.length
        bucket[len] = arr[i]
        for (let j = len - 1; j >= 0; j--){
            if (bucket[j] < arr[i]){
                bucket[j + 1] = bucket[j]
            } else {
                bucket[j + 1] = arr[i]
                break
            }
        }
    }

    let p = 0
    for (let i = 0; i < buckets.length; i++){
        for (let j = 0; j < buckets[i].length; j++){
            arr[p] = buckets[i][j]
            p++
        }
    }

    return arr

算法属性

最优时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
Ω(n+k) Θ(n+k) O(n+k) O(n+k) 稳定

小结

这些非比较排序主要依靠了整数可以直接映射到存储空间的特性，只有在部分情况下才会有用，而最常用到的依然还是比较排序

END

2019-03-08 完成

2019-03-06 立项