这里实现的更一般的计数排序是原地排序吗?

这里实现的更一般的计数排序是原地排序吗?

在网上查到的解释:原地排序不需要开额外的空间,只需要少量的辅助变量即可以完成排序。


我个人的感觉,非原地排序,一般需要创建一个和待排序数组一样大的临时数组。像归并排序和后面章节讲到的稳定的计数排序。


本节的计数排序,只有一个域,稳定性没有意义。

对于leetcode 75 颜色分类问题,创建了一个3个元素的数组,还可以认为是三个辅助变量。

但是,有时数据范围很大,甚至等于或者大于数据规模n,这时需要开辟一个很大的空间才行,所以产生疑惑,这算是原地排序吗?是否是原地排序还取决于开辟的空间和数据规模的大小关系吗?


因为有些题目,像leetcode75问题,就要求了使用原地排序。因此想问下老师。

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

1回答
liuyubobobo 2021-12-29 14:07:40

1


计数排序不是原地排序。原因你的分析是正确的。在最差情况下,n 个数值有 n 个取值可能,那么至少要开 n 的空间,这个空间消耗是不可忽略的。


当然,如果排序的元素特殊,比如"颜色分类问题",取值可能只有三个,那么使用计数排序是合理的(甚至是最佳的)选择。(并且在这个特殊的情况下,这个空间消耗可以忽略不计。)但不能因为特殊的例子,而一般性地叫计数排序是原地的。这就好比在特殊情况下,插入排序可以是 O(n) 的,但我们不能说插入排序是 O(n) 的。



2


计数排序的稳定性是有意义的,它是基数排序的基础。这一点在后续课程会专门介绍:)



继续加油!:)

  • 提问者 假蛙工程师 #1

    明白了,感谢老师。使用时间复杂度做类比,加深了我对原地排序的理解。

    2021-12-30 10:32:54
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师