如果只有从1到n的元素，是否可以对O（n）中的数组进行排序？

假设数组中元素的比较采用O（n），当元素从1开始到n时，是否可以对O（n）中的数组进行排序？如果只有从1到n的元素，是否可以对O（n）中的数组进行排序？

我们需要创建一个这样的算法，但不知道它是否可能。我可以想到O（n^2）中的一个。我不是要求算法，会花费我的时间来创建一个算法，但需要知道它是否可能。

来源

2016-06-07 frytkii

重复包含或不包含？ –

比较需要O（n）？ – gexicide

https://en.wikipedia.org/wiki/Sorting_algorithm查看'Non-comparison sorts' – MBo

这是绝对有可能的话，你只需创建一个计数器阵列和计数我发生时间元素的数量，因为元素范围从至ñ，你知道这个计数器的长度为n。

接下来是生成步骤，在这里简单地生成ķ_我元件我如果已经遇到ķ_我这样的元件。在Java中

示例代码：

int[] data = {5,1,2,4,5,1,2,3}; 

//assuming data contains only values from 1 to n (included) with n the length 
public static int[] sort_int_limited (int[] data) { 
    int n = data.length; 
    int[] counters = new int[data.length]; 

    //counter phase 
    for(int i = 0; i < n; i++) { 
     counters[data[i]-1]++; 
    } 

    //generate phase 
    int k = 0; 
    for(int i = 0; i < n; i++) { 
     for(int j = 0; j < counters[i]; j++) { 
      data[k++] = i+1; 
     } 
    } 

    return data; 
}

jDoodle demo

由于@Aivaen在his/her comment说，这种算法被称为排序计数。

来源

2016-06-07 18:09:54

顺便说一下，这种算法被称为[计数排序]（https://en.wikipedia.org/wiki/Counting_sort）。 – Aivean

@Aivean：我已将它添加到答案中。不知道名称，但最终这个算法是相当简单的，因此已经存在。 –

非常感谢大家与我分享您的想法和知识，非常感谢！ – frytkii

是“桶排序”：尺寸的申报数组n称之为ARR，其设置为零，

2.对于给定的输入阵列中的每个值：

add one in arr in the index that is equal to the value

声明新的数组出： DECLARE 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-07 18:08:33

不清楚“数组中元素的比较需要O（n）”是什么意思。如果一个数组的大小是“s”，那么可能的比较次数是一次取2个数。

可以在O（s）时间执行的排序不会比较元素，通常它们会对它们进行计数，或者它们将元素值用作索引。

这可能是一个技巧性的问题，因为没有指定元素的数量。让s =数组的大小，然后计数排序可以在O（s）时间（不是O（n）时间）对数组进行排序。

来源

2016-06-08 07:34:57 rcgldr

如果只有从1到n的元素，是否可以对O（n）中的数组进行排序？

回答

相关问题