使用Java代碼對1到100個整數進行排序

Question

給定1到9之間的1百萬整數的集合。如何以有效的方式對它們進行排序？

Input: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8] 
Output: [1,2,2,3,4,4,5,5,5,6,6,7,8,8,9] 

Answer 1

對於大的投入，Java的Collections.sort()使用TimSort，它運行在O（N日誌（N））。 如果您希望它運行得更快，那麼讓我們說線性時間，比您應該使用非基於比較的排序算法。

由於您的整數範圍比要排序的項目數小得多，所以這是Counting Sort的完美用法。

正在k = 9（範圍從1-9）和N = 1 million。您的運行時間將爲O（k + N）。

Answer 2

創建10個數組（或10個數組的數組），每個數字一個，迭代您的輸入數組並將每個數字添加到相應的數組。最後，結合所有的數組。

Answer 3

輸入：[1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]
輸出：[1,2,2,3， 4,4,5,5,5,6,6,7,8,8,9]

這可以用O（n）時間和O（k）空間求解。

由於給出的範圍是9，我們可以創建尺寸9 + 1的數組，其中每個索引將一個數的發生存儲在輸入數組

TempArray = [0 1 2 1 2 3 2 1 2 1] 索引0 1 2 3 4 5 6 7 8 9

所有您需要做的就是讀取tempArray並填充數據回輸入。

索引1處的值爲1，所以我們只會添加一個元素。

索引2的值爲2，所以我們將添加兩個時間二。

索引3的值是1，所以我們只會添加三個。在指數4

值是2，所以我們會以這種方式，你可以覆蓋原來的數組只添加兩個四 時間....

。

T（O（n））的 S（O（k））的

讓我知道如果您有任何困惑。

這裏是相同的C＃代碼：

int[] input = new int[15] { 1, 2, 5, 4, 7, 8, 9, 6, 5, 4, 2, 3, 6, 5, 8 }; 
    int k = 9; 

    int[] temp = new int[k + 1]; 
    for (int index = 0; index < input.Length; index++) 
    { 
     temp[input[index]]++; 
    } 


    int i = 0; // used for input index 
    for (int index = 0; index < temp.Length; index++) 
    { 
     while (temp[index]-- != 0) // redusing count value after updating the index into input array 
      input[i++] = index; 
    } 

    for (int index = 0; index < input.Length; index++) 
    { 
     Console.Write(" {0} ", input[index]); 
    }