C#列表元素重复次数统计代码异常问题求助

我知道这段代码并非最优，但现在遇到一个问题：尝试参考计数排序思路，通过在listIndex对应索引位置累加1来统计列表元素重复次数，结果出现异常——元素重复n次时，统计结果为n²（比如重复2次显示4，重复3次显示9）。以下是代码、期望输出和实际输出，求排查原因。

代码 #

List<int> list = new List<int>() { 1, 3, 3, 6, 3, 6, 10 };
List<int> listIndex = new List<int>();
int yts = 0;

for (int i = 0; i < list.Count; i++)
{
    if (list[i] > yts)
    {
        yts = list[i];
    }
}
for(int i = 0; i <= yts; i++)
{
    listIndex.Add(0);
}

for (int u = 0; u < list.Count; u++)
{
    for (int j = 0; j < list.Count; j++)
    {
        if (list[u] == list[j])
        {
            int num = list[u];
            listIndex[num] = listIndex[num] + 1;
        }
    }
}

foreach (int i in listIndex)
{
    Console.WriteLine(i);
}

期望输出 #

listIndex[0] = 0
listIndex[1] = 1
listIndex[2] = 0
listIndex[3] = 3
listIndex[4] = 0
listIndex[5] = 0
listIndex[6] = 2
listIndex[7] = 0
listIndex[8] = 0
listIndex[9] = 0
listIndex[10] = 1

实际输出 #

listIndex[0] = 0
listIndex[1] = 1
listIndex[2] = 0
listIndex[3] = 9
listIndex[4] = 0
listIndex[5] = 0
listIndex[6] = 4
listIndex[7] = 0
listIndex[8] = 0
listIndex[9] = 0
listIndex[10] = 1

问题原因 #

你嵌套了两层循环遍历原列表，导致每个重复元素被重复计数。比如元素3出现3次，外层循环每遇到一次3（共3次），内层循环都会遍历整个列表找到3次匹配，每次匹配都给listIndex[3]加1，总共3×3=9次累加，结果就是9，正好是n²。

修复方案 #

去掉内层循环，直接遍历原列表一次，每次取出元素后给对应索引位置加1即可，这才是计数排序统计次数的正确思路：

List<int> list = new List<int>() { 1, 3, 3, 6, 3, 6, 10 };
List<int> listIndex = new List<int>();
int yts = 0;

for (int i = 0; i < list.Count; i++)
{
    if (list[i] > yts)
    {
        yts = list[i];
    }
}
for(int i = 0; i <= yts; i++)
{
    listIndex.Add(0);
}

// 替换原嵌套循环为单层循环
for (int u = 0; u < list.Count; u++)
{
    int num = list[u];
    listIndex[num]++;
}

foreach (int i in listIndex)
{
    Console.WriteLine(i);
}

这段代码执行后会得到你期望的输出，每个元素的出现次数被正确统计。

内容的提问来源于stack exchange，提问作者Reynaldo Delmonte