首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如果只有从1到n的元素,就可以对O(n)中的数组进行排序吗?

问如果只有从1到n的元素,就可以对O(n)中的数组进行排序吗?
EN

Stack Overflow用户
提问于 2016-06-07 18:01:41
回答 2查看 138关注 0票数 2

假设数组中元素的比较采用O( n ),当数组中的元素从1开始到n时,可以对数组进行排序吗?

我们需要创建这样的算法,但不知道它是否可行。我能想到O(n^2)中的一个。我不是要求算法,我会花时间来创建一个,但需要知道它是否有可能。

EN

回答 2

Stack Overflow用户

发布于 2016-06-07 18:08:33

是的“桶排序”:声明大小为n的数组称为arr,将其设置为零,

2.对于给定输入数组中的每个值:

代码语言:javascript
复制
  add one in arr in the index that is equal to the value

声明新数组:声明int k =0

3.输入数组中的I

代码语言:javascript
复制
if arr[inputarray[i]>0 do:

    1.out[k]= arr[i]
    2.arr[inputarray[i] = arr[inputarray[i] -1
    3. k=k+1

返回

票数 1
EN

Stack Overflow用户

发布于 2016-06-08 07:34:57

还不清楚“数组中元素的比较”是什么意思。如果数组的大小是"s",那么可能的比较数是一次取2的东西。

可以在O(s)时间内执行的排序不对元素进行比较,通常它们会对元素进行计数,或者使用元素值作为索引。

这可能是刁钻的问题,因为没有指定元素的数量。让s=数组的大小,然后计数排序可以按O(s)时间(而不是O(n)时间)对数组进行排序。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/37686263

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档