如果只有從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）中的數組進行排序？

回答

相關問題