这里实现的更一般的计数排序是原地排序吗?
在网上查到的解释:原地排序不需要开额外的空间,只需要少量的辅助变量即可以完成排序。
我个人的感觉,非原地排序,一般需要创建一个和待排序数组一样大的临时数组。像归并排序和后面章节讲到的稳定的计数排序。
本节的计数排序,只有一个域,稳定性没有意义。
对于leetcode 75 颜色分类问题,创建了一个3个元素的数组,还可以认为是三个辅助变量。
但是,有时数据范围很大,甚至等于或者大于数据规模n,这时需要开辟一个很大的空间才行,所以产生疑惑,这算是原地排序吗?是否是原地排序还取决于开辟的空间和数据规模的大小关系吗?
因为有些题目,像leetcode75问题,就要求了使用原地排序。因此想问下老师。
11
收起
正在回答 回答被采纳积分+1
1回答
liuyubobobo
2021-12-29 14:07:40
1
计数排序不是原地排序。原因你的分析是正确的。在最差情况下,n 个数值有 n 个取值可能,那么至少要开 n 的空间,这个空间消耗是不可忽略的。
当然,如果排序的元素特殊,比如"颜色分类问题",取值可能只有三个,那么使用计数排序是合理的(甚至是最佳的)选择。(并且在这个特殊的情况下,这个空间消耗可以忽略不计。)但不能因为特殊的例子,而一般性地叫计数排序是原地的。这就好比在特殊情况下,插入排序可以是 O(n) 的,但我们不能说插入排序是 O(n) 的。
2
计数排序的稳定性是有意义的,它是基数排序的基础。这一点在后续课程会专门介绍:)
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星