blocks|key|3922823|text|您可以使用counting+sort。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3922824|3922825|计数排序(有时称为超排序或数学排序)是一种排序算法，它(类似于桶排序)利用了知道要排序的数组(数组A)中数字的范围。|blockquote|3922826|3922827|计数排序是一种稳定的排序，其运行时间为n%2Bk(Θ)，其中n和k分别是数组A(输入数组)和C(计数数组)的长度。为了使此算法有效，k不能比n大很多。|3922828|3922829|在这种情况下，k是100，n是1000000。|3922830|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Counting_sort^0|5|D|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|D|3|-4|5|6|7|Z|8|@]|9|@]|C|$]]|$1|E|3|F|5|G|7|10|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|11|8|@]|9|@]|C|$]]|$1|I|3|J|5|6|7|12|8|@]|9|@]|C|$]]|$1|K|3|-4|5|6|7|13|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|14|8|@]|9|@]|C|$]]|$1|N|3|-4|5|6|7|15|8|@]|9|@]|C|$]]]|O|$P|$5|Q|R|S|C|$T|U]]]]

You can use <a href="http://en.wikipedia.org/wiki/Counting_sort" rel="noreferrer">counting sort</a>.
<blockquote>
Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A).
Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.
</blockquote>
In this case k is 100 and n is 1000000.

blocks|key|773342|text|在这种情况下，计数排序将是显而易见的选择。是的，如果实现得当，它应该具有线性复杂度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|773343|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A counting sort would be the obvious choice under these circumstances. Yes, properly implemented it should have linear complexity.

blocks|key|3922845|text|如何只计算每个整数的出现次数，然后将它们全部打印出来。听起来像O(n)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3922846|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

how about just counting the occurrence of each integer and then printing them all. sounds like O(n)

blocks|key|2514910|text|我假设，你的意思是你想实现一个小的O(n)；那么桶排序将是最快的。事实上，既然你知道整数的范围，那么使用桶排序就变成了一个计算数字出现次数的问题，这可以在O(n)，即线性时间内完成。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2514911|所谓的计数排序只是存储桶排序的一种特殊情况。|2514912|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

I assume, you mean you want to achieve a small O(n); then bucket sort would be fastest. In fact, since you know the range of the integers, then using bucket sort simply becomes a problem of counting the occurrences of the numbers which can be done in O(n), i.e. linear time.

The so-called counting sort is simply a special case of bucket sort.

blocks|key|3922795|text|使用计数排序，如果范围固定且较小(如1..100：)，则得到O(N)。)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3922796|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

With counting sort you get O(N) if the range is fixed and small (like 1..100 :))

blocks|key|2514937|text|对于任何感兴趣的人，在阅读答案之前，我很快就把这段Ruby拼凑在一起：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2514938|module+Enumerable
++def+counting_sort(k)
++++reduce(Array.new(k%2B1,+0))+{%7Ccounting,+n%7C+counting.tap+{+counting[n]+%2B=+1+}}.
++++map.with_index+{%7Ccount,+n%7C+[n]+*+count+}.flatten
++end
end

ary+=+Array.new(1_000_000){+rand(100)+%2B+1+}
ary.counting_sort(100)+#+I'll+spare+you+the+output+:-)|code-block|syntax|javascript|2514939|我甚至不知道它还有名字。它应该把这个想法传达给那些从未见过Ruby的人。(您唯一需要知道的是，K组合子在Ruby语言中拼写为tap。)|offset|length|style|CODE|2514940|而且它真的非常快，尽管不幸的是我还没有能够击败内置的手工优化的O(N+Log+N)排序，它是用MRI用C语言编写的，YARV和JRuby是用JRuby编写的。|2514941|entityMap^0|0|0|1Q|3|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@$I|T|J|U|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

For anyone interested, I quickly threw together this piece of Ruby, before reading the answers:

<pre><code>module Enumerable
 def counting_sort(k)
 reduce(Array.new(k+1, 0)) {|counting, n| counting.tap { counting[n] += 1 }}.
 map.with_index {|count, n| [n] * count }.flatten
 end
end

ary = Array.new(1_000_000){ rand(100) + 1 }
ary.counting_sort(100) # I'll spare you the output :-)
</code></pre>

I didn't even know it had a name. It should convey the idea even to someone who has never seen Ruby before. (The only thing you need to know is that the K combinator is spelled <code>tap</code> in Ruby.)

And it really is pretty darn fast, although unfortunately I have not been able to beat the builtin hand-optimized O(n&thinsp;log&thinsp;n) sort, which is written in C in MRI and YARV and Java in JRuby.

blocks|key|3922944|text|以下是scala中的计数排序：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3922945|val+res+=+Array.fill+(100)(0)
val+r+=+util.Random+
//+generate+data+to+sort
val+nums+=+for+(i+<-+1+to+1000*1000)+yield+r.nextInt+(100)
for+(i+<-+nums)+res(i)+%2B=+1
println+(res.mkString+("+"))+|code-block|syntax|javascript|3922946|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is a counting sort in scala:

<pre><code>val res = Array.fill (100)(0)
val r = util.Random 
// generate data to sort
val nums = for (i &lt;- 1 to 1000*1000) yield r.nextInt (100)
for (i &lt;- nums) res(i) += 1
println (res.mkString (" ")) 
</code></pre>

blocks|key|2515019|text|使用基数排序(在Ruby中)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2515020|def+sort(array)
sorted_array+=+Array.new(100,[])
array.each+do+%7Ct%7C
sorted_array[t-1]+=+sorted_array[t-1]+%2B+[t]
end
sorted_array.flatten!
end|code-block|syntax|javascript|2515021|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Using Radix Sort (In Ruby):

<pre><code>def sort(array)
sorted_array = Array.new(100,[])
array.each do |t|
sorted_array[t-1] = sorted_array[t-1] + [t]
end
sorted_array.flatten!
end
</code></pre>

Notes: I've thought about Radix sort, bucket sort, counting sort.

Is there anyway to achieve big O(n)?

What is the fastest way to sort 1 million integers when integers are from the range [1,100]?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

注意:我已经考虑过基数排序，桶排序，计数排序。有没有实现大O(n)的方法？

问当整数在[1,100]范围内时，对100万个整数进行排序的最快方法是什么？
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问当整数在[1,100]范围内时，对100万个整数进行排序的最快方法是什么？EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问当整数在[1,100]范围内时，对100万个整数进行排序的最快方法是什么？
EN