c# - 排序而不比较元素

Question

给定数组 5 的大小，其中包含五个数字，将它们从小到大排序，不进行比较。（提示，访问时间 O(n)

我试图搜索很多，但不知道如何做到这一点。O(n)，表示哪个算法/数据结构。我不知道。

Answer 1

我想您需要Counting sort，它具有线性时间，但需要一些内存并且取决于初始数组的最小/最大值

Answer 2

计数排序会为您执行此操作，尽管如果我在接受采访并且在现场我可能会做类似下面的事情，这有点相似，因为我永远记不起这些“经典”算法！

这里的关键思想是使用每个实际的未排序整数值作为包含 N 个元素的目标数组的索引，其中 N 是最大值。要排序的值。

我正在使用一个简单的类来记录值和它发生的次数，因此如果您需要保留在原始数组中多次出现的离散值，您可以从中重建一个实际数组。

因此，您需要做的就是遍历未排序的数组一次，将每个值放入目标数组中的相应索引中，并且（忽略空元素）您的值已经从最小到最大排序，而无需将它们相互比较。

（我个人不喜欢这样的面试问题，答案是“哦，使用计数排序”或其他什么 - 我希望问这个问题的面试官真的有兴趣看看你用什么方法来解决一个新问题，无论您是否得到严格正确的答案）

下面的性能是 O(n)，这意味着它在线性时间内运行（1 个元素需要 X 时间，10 个元素需要 10X 等）但是如果最大元素很大，它可以使用大量内存，不能在地方排序，只适用于原语，这不是我希望在生产代码中看到的东西:)

void Main()
{
   //create unsorted list of random numbers
    var unsorted = new List<int>();
    Random rand = new Random();
    for(int x=0;x<10;x++)
    {
     unsorted.Add(rand.Next(1,10));
    }
    //create array big enough to hold unsorted.Max() elements
    //note this is indirectly performing a comparison of the elements of the array
    //but not for the sorting, so I guess that is allowable :)
    var sorted = new NumberCount[unsorted.Max()+1];
    //loop the unsorted array 
    for (int index=0;index<unsorted.Count;index++)
    {
   //get the value at the current index and use as an index to the target array
        var value = unsorted[index];
        //if the sorted array contains the value at the current index, just increment the count
        if (sorted[value]!=null && sorted[value].Value!=0)
        {
           sorted[value].Count++;
        }
        else
        {
        //insert the current value in it's index position
         sorted[value]=new NumberCount{Value=value,Count=1};          
        }
    }
    //ignore all elements in sorted that are null because they were not part of the original list of numbers.
    foreach (var r in sorted.Where(r=>r!=null))
    {
       Console.WriteLine("{0}, occurs {1} times",r.Value,r.Count);
    }
}

//just a poco to hold the numbers and the number of times they occurred.
public class NumberCount
{
  public int Value{get;set;}
  public int Count{get;set;}
}