假设数组中元素的比较采用O( n ),当数组中的元素从1开始到n时,可以对数组进行排序吗?
我们需要创建这样的算法,但不知道它是否可行。我能想到O(n^2)中的一个。我不是要求算法,我会花时间来创建一个,但需要知道它是否有可能。
发布于 2016-06-07 18:08:33
是的“桶排序”:声明大小为n的数组称为arr,将其设置为零,
2.对于给定输入数组中的每个值:
add one in arr in the index that is equal to the value声明新数组:声明int k =0
3.输入数组中的I
if arr[inputarray[i]>0 do:
1.out[k]= arr[i]
2.arr[inputarray[i] = arr[inputarray[i] -1
3. k=k+1返回
发布于 2016-06-08 07:34:57
还不清楚“数组中元素的比较”是什么意思。如果数组的大小是"s",那么可能的比较数是一次取2的东西。
可以在O(s)时间内执行的排序不对元素进行比较,通常它们会对元素进行计数,或者使用元素值作为索引。
这可能是刁钻的问题,因为没有指定元素的数量。让s=数组的大小,然后计数排序可以按O(s)时间(而不是O(n)时间)对数组进行排序。
https://stackoverflow.com/questions/37686263
复制相似问题