c# - 对 0、1 和 2 的数组进行排序（进一步优化）

Question

下面是一个非常简单的代码，它对0s、1s 和 2s的数组进行排序 。我相信它的时间复杂度是O(N)，对吧？如何进一步改进该算法以将时间复杂度降低到O(logN)左右？

//Input:  0 2 1 2 0
//Output: 0 0 1 2 2
    public static int[] SortArray012(int[] array)
        {
            Dictionary<int, int> result = new Dictionary<int, int>(3);
            int[] sortedResult = new int[array.Length];
            int i = 0;

            foreach(int no in array)
            {
                if (result.ContainsKey(no))
                    result[no]++;
                else
                    result.Add(no, 1);
            }

            for (; i < result[0]; i++)
                sortedResult[i] = 0;
            for (; i < result[0] + result[1]; i++)
                sortedResult[i] = 1;
            for (; i < result[0] + result[1] + result[2]; i++)
                sortedResult[i] = 2;

            return sortedResult;
        }

标签： c#algorithm

Answer 1

这是计数排序的示例。虽然据我所知无法降低渐近复杂度，但您可以专注于减少常数。例如不需要构造字典，数组就可以了。如果我们保证我们只会看到 1,2 和 0，那么就不需要 if 语句。我们还可以使用两个 for 循环而不是三个来生成结果

int[] test = {1,1,0,2,1,0};
int[] count = {0,0,0};
int[] result = new int[test.Length];
foreach(int no in test){
    count[no]++;    
}
int i = 0;
int k = 0;
foreach(int c in count){
    for(int j = 0; j < c; j++){
        result[k++] = i;    
    }
    i++;
}