按O（n）时间排序？ [英] Sorting in O(n) time?

问题描述

我在这个问题上停留了2个星期。知道如何处理它吗？

I'm stuck on this problem(2 weeks). Any idea of how to approach it?.

让L是n个不同整数的列表，并假设L的x的元素在[1,750]范围内。设计一个线性排序算法来排序L

Let L be a list of n different integer numbers, assume that the elements of x of L are in the range [1,750]. Design a linear ordering algorithm to order the elements of L

我已经尝试过插入排序的元素。但是我不确定我的方法是否正确：

I already tried with insertion sort. But i'm not sure if my approach is right:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

复杂度=> O（2n）= O（n）

Complexity => O(2n) = O(n)

推荐答案

尝试使用Radix排序- http://en.wikipedia.org/ wiki / Radix_sort

Try Radix sort - http://en.wikipedia.org/wiki/Radix_sort

如果您认为750为常数，则排序为O（n）。

If you consider given 750 as constant, it sorts at O(n).

基于比较的排序不能少于O（nlogn）进行排序，但是如果值的数量受D限制，则可以将O（D * n）或O（n）排序（如果您将D视为常数）

Comparison based sorting can't sort in less than O(nlogn), but if number of values is bounded by D, you can sort in O(D*n), or O(n) if you consider D as constant.

这篇关于按O（n）时间排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！