计数排序适配非0最小值范围的问题排查与优化

Let's break down the key issues in your code and fix them one by one—your implementation has several logical missteps that prevent it from working with non-zero minimum values:

Key Issues & Fixes #

1. findMinValue doesn't actually find the minimum

Your current function just returns the first element of the array, not the true minimum. We need to traverse the entire array to find the smallest value:

public static int findMinValue(int[] List) {
    int min = List[0];
    for (int i = 1; i < List.Length; i++) {
        if (List[i] < min) {
            min = List[i];
        }
    }
    return min;
}

2. You're fetching the minimum from the wrong array

In your countingsort method, you call findMinValue(countArray)—this is a critical mistake. The countArray is initialized to all zeros, so you'll always get 0 as the minimum. You need to get the minimum from the original unsorted list:

int min = findMinValue(List); // Correct: use the input list, not the count array

3. Count array is unnecessarily large and uses wrong indexing

Using max + 1 for the count array length wastes memory when the minimum is non-zero. Instead, calculate the length as max - min + 1 to only cover the actual range of values. You also need to map original values to 0-based indices in the count array using value - min:

// Correct count array size: covers from min to max inclusive
int[] countArray = new int[max - min + 1];
Array.Fill(countArray, 0); // Initialize all counts to 0

// Count elements using mapped indices
for (int x = 0; x < List.Length; x++) {
    int mappedIndex = List[x] - min;
    countArray[mappedIndex]++;
}

4. Restoring sorted values uses wrong mapping

When rebuilding the sorted list, you need to map the count array's indices back to the original values with index + min:

int index = 0;
for (int y = 0; y < countArray.Length; y++) {
    for (int j = 0; j < countArray[y]; j++) {
        List[index] = y + min; // Map back to original value
        index++;
    }
}

5. Typo in the timer output

You labeled the time as "Basic Selection Sort" instead of "Counting Sort"—easy fix!

Full Corrected Code #

using System;
using System.Diagnostics;

public class CountingSortFix {
    public static int findMinValue(int[] List) {
        int min = List[0];
        for (int i = 1; i < List.Length; i++) {
            if (List[i] < min) {
                min = List[i];
            }
        }
        return min;
    }

    static void countingsort(int[] List, int max) {
        Stopwatch timer = new Stopwatch();
        timer.Start();

        int min = findMinValue(List);
        int[] countArray = new int[max - min + 1];
        Array.Fill(countArray, 0);

        // Count element occurrences
        for (int x = 0; x < List.Length; x++) {
            int mappedIndex = List[x] - min;
            countArray[mappedIndex]++;
        }

        // Rebuild sorted array
        int index = 0;
        for (int y = 0; y < countArray.Length; y++) {
            for (int j = 0; j < countArray[y]; j++) {
                List[index] = y + min;
                index++;
            }
        }

        Display(List);
        DisplayCount(countArray);
        timer.Stop();
        Console.WriteLine("Time Taken for Counting Sort is {0} milliseconds", timer.ElapsedMilliseconds);
    }

    public static void Display(int[] Array) {
        Console.WriteLine("Sorted Array:");
        foreach (int num in Array) {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }

    public static void DisplayCount(int[] Array) {
        Console.WriteLine("Elements in count array is {0}", Array.Length);
    }

    // Test with 20000 integers in 1000-9999 range
    public static void Main() {
        Random rand = new Random();
        int[] testList = new int[20000];
        int max = 9999;
        for (int i = 0; i < testList.Length; i++) {
            testList[i] = rand.Next(1000, max + 1);
        }
        countingsort(testList, max);
    }
}

Why This Works #

• We correctly identify the actual minimum value of the input list, so we only work with the relevant range of values.
• The count array is sized exactly to fit the range [min, max], eliminating unnecessary memory usage.
• Value-index mapping ensures we never try to access out-of-bounds indices in the count array, even when the minimum is far from 0.

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