线性排序:

线性排序即排序算法的时间复杂度是线性的,也就是 O(n)。桶排序、计数排序、基数排序这三个算法是不基于比较的排序算法,都不涉及元素之间的比较操作。

计数排序(Counting sort)

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的空间复杂度和时间复杂度为Ο(n+k),其中k是整数的范围;快于任何比较排序算法。

计数排序是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)。

计数排序核心

在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

动画演示:

jishupaixu.gif

总结:

计数排序只能用在数据范围不大的场景中,如果数据范围 k 比要排序的数据 n 大很多,就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。

Python代码:

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

 Go 代码实

func countingSort(arr []int, maxValue int) []int {
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen) // 初始为0的数组

    sortedIndex := 0
    length := len(arr)

    for i := 0; i < length; i++ {
        bucket[arr[i]] += 1
    }

    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }

    return arr
}

参考网址:

https://sort.hust.cc/8.countingsort

https://www.cxyxiaowu.com

https://time.geekbang.org/column/article/41913

https://baike.baidu.com/item/计数排序/8518144

本文地址: http://chenxm.cc/article/982.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: python 排序算法——线性排序之桶排序
下一篇: python 排序算法——线性排序之基数排序(Radix sort)
发表评论

还没有留言,还不快点抢沙发?