使用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]); 
    }