线性排序:
线性排序即排序算法的时间复杂度是线性的,也就是 O(n)。桶排序、计数排序、基数排序这三个算法是不基于比较的排序算法,都不涉及元素之间的比较操作。
计数排序(Counting sort)
计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的空间复杂度和时间复杂度为Ο(n+k),其中k是整数的范围;快于任何比较排序算法。
计数排序是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)。
计数排序核心
在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
动画演示:
总结:
计数排序只能用在数据范围不大的场景中,如果数据范围 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
还没有留言,还不快点抢沙发?