如果數組有問題，可以在O（n）中排序

如果數組只包含k ∈ ℕ>0（k是一個常數）不同的元素，可以在最壞情況下運行時排序數組O(n)？如果數組有問題，可以在O（n）中排序

這個假設是它需要一個恆定的時間來比較其中包含n個元素的數組。

首先我想了解這個任務，他們想要什麼？我明白這個假設。但究竟是什麼意思k ∈ ℕ>0（k是一個常數）不同的元素？

這是否意味着我們得到一個數組，它的大小是k，因爲它說ℕ>0數組大小不能爲0？那是對的嗎？如果是這樣，我不明白他們爲什麼不只是說與n元素而不是陣列。

無論如何，這就是我的理解，我會說這是不可能的排序這個數組在最壞的情況下運行時間O(n)，因爲如果我們看看桶排序/基數排序等，它可以在O(n*logn)完成。

來源

2016-06-12 itaminul

*可能在最壞的情況下對運行時間進行排序O（n）*最壞的情況下，您需要將列表中的每個項目與' log（n）'其中 –

但假設說比較是在恆定時間內完成的，所以O（n）而不是O（log n） – itaminul

這是你的意思嗎？ https://en.m.wikipedia.org/wiki/Counting_sort –

如果您知道這些值，您可以通過將數字放入「存儲桶」中對數組進行排序。對於每個值，您創建存儲桶並在迭代時向該存儲桶添加數字。你這所有的數字和只有一次，因此它在O(n)

例如0-9只具有數字做，你可以如下

public class SortInBucket { 
    public static void main(String[] args) { 
     int[] x = {0,5,1,1,1,1,7,9,3,2,1,2,5,6}; 
     System.out.println("Result of sorting: " + Arrays.toString(sortInBuckets(x))); 
    } 

    public static int[] sortInBuckets(int[] arr) { 
     List<List<Integer>> sortedNumbers = new ArrayList<>(); 
     int[] sortedArr = new int[arr.length]; 
     // create buckets 0 - 9 
     for (int i = 0; i < 10; i++) { 
      sortedNumbers.add(new ArrayList<>()); 
     } 

     for (int i = 0; i < arr.length; i++) { 
      System.out.println("Found number " + arr[i] + " puting index " + i + " to bucket " + arr[i]); 
      sortedNumbers.get(arr[i]).add(i); 
      System.out.println("Bucket " + arr[i] + " is having " +sortedNumbers.get(arr[i]).size() + " numbers now."); 
     } 

     System.out.println(); 
     System.out.println("The sortedNumbers (list with buckets) looks like following: " +sortedNumbers); 

     //just going through buckets and adding its numbers to sortedArr 
     int sortedIndex = 0; 
     for (List<Integer> bucket : sortedNumbers){ 
      for (Integer num : bucket){ 
       sortedArr[sortedIndex] = arr[num]; 
       sortedIndex++; 
      } 
     } 

     return sortedArr; 
    } 
}

上面的代碼有排序呢此輸出

Found number 0 puting index 0 to bucket 0 
Bucket 0 is having 1 numbers now. 
Found number 5 puting index 1 to bucket 5 
Bucket 5 is having 1 numbers now. 
Found number 1 puting index 2 to bucket 1 
Bucket 1 is having 1 numbers now. 
Found number 1 puting index 3 to bucket 1 
Bucket 1 is having 2 numbers now. 
Found number 1 puting index 4 to bucket 1 
Bucket 1 is having 3 numbers now. 
Found number 1 puting index 5 to bucket 1 
Bucket 1 is having 4 numbers now. 
Found number 7 puting index 6 to bucket 7 
Bucket 7 is having 1 numbers now. 
Found number 9 puting index 7 to bucket 9 
Bucket 9 is having 1 numbers now. 
Found number 3 puting index 8 to bucket 3 
Bucket 3 is having 1 numbers now. 
Found number 2 puting index 9 to bucket 2 
Bucket 2 is having 1 numbers now. 
Found number 1 puting index 10 to bucket 1 
Bucket 1 is having 5 numbers now. 
Found number 2 puting index 11 to bucket 2 
Bucket 2 is having 2 numbers now. 
Found number 5 puting index 12 to bucket 5 
Bucket 5 is having 2 numbers now. 
Found number 6 puting index 13 to bucket 6 
Bucket 6 is having 1 numbers now. 

The sortedNumbers (list with buckets) looks like following: [[0], [2, 3, 4, 5, 10], [9, 11], [8], [], [1, 12], [13], [6], [], [7]] 
Result of sorting: [0, 1, 1, 1, 1, 1, 2, 2, 3, 5, 5, 6, 7, 9]

正如由JF塞巴斯蒂安和Steve314，即做噸alghoritms提到他被稱爲基數排序（更廣泛的alghorithm）或計數排序（不是「強」，但更簡單，可用於這個例子）。

來源

2016-06-12 11:14:02 libik

我想看看這個算法分類N個數字。 –

@EdHeal'foreach x（array）{bucket [x] ++; } foreach x（indices（bucket））{foreach i（range（bucket [x]））{output（x）; }}' – melpomene

對於這個問題，'x'與'n'的大小是否相同？ –

不，數組的大小爲n，但它可以包含重複的元素。數組中只有k個獨特元素。（或換句話說，n - k是陣列中的重複項的數量。）

來源

2016-06-12 11:15:25 melpomene

如果數組有問題，可以在O（n）中排序

回答

相關問題