How to implement counting sorting algorithm in C#

How to implement the counting sort algorithm in C

#Counting sort is a simple but effective sorting algorithm that can achieve O(n k) time complexity Sort a set of integers, where n is the number of elements to be sorted and k is the range of elements to be sorted.

The basic idea of ​​counting sorting is to create an auxiliary array to count the number of occurrences of each element in the sequence to be sorted. Then, by performing a sum operation on the auxiliary array, the position of each element in the ordered sequence is obtained. Finally, based on the statistical results of the auxiliary array, the elements are put back into the original array to complete the sorting.

The following is a specific code example for implementing the counting sorting algorithm in C#:

using System;

class CountingSort
{
    public static void Sort(int[] array)
    {
        if (array == null || array.Length == 0)
        {
            return;
        }

        // 找到待排序序列中的最大值和最小值
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] < min)
            {
                min = array[i];
            }
            if (array[i] > max)
            {
                max = array[i];
            }
        }

        // 创建辅助数组count，用于统计待排序序列中每个元素的出现次数
        int[] count = new int[max - min + 1];

        // 统计每个元素的出现次数
        for (int i = 0; i < array.Length; i++)
        {
            count[array[i] - min]++;
        }

        // 对辅助数组进行求和操作，得到每个元素在有序序列中的位置
        for (int i = 1; i < count.Length; i++)
        {
            count[i] += count[i - 1];
        }

        // 创建临时数组，用于存储排序结果
        int[] sortedArray = new int[array.Length];

        // 根据辅助数组的统计结果，将元素放回原始数组中
        for (int i = array.Length - 1; i >= 0; i--)
        {
            int index = count[array[i] - min] - 1;
            sortedArray[index] = array[i];
            count[array[i] - min]--;
        }

        // 将排序结果拷贝回原始数组
        Array.Copy(sortedArray, array, array.Length);
    }

    // 测试计数排序算法
    static void Main(string[] args)
    {
        int[] array = { 5, 2, 9, 3, 1, 6, 8, 4, 7 };
        Console.WriteLine("原始数组：");
        PrintArray(array);
        Sort(array);
        Console.WriteLine("排序结果：");
        PrintArray(array);
    }

    // 打印数组
    static void PrintArray(int[] array)
    {
        foreach (int element in array)
        {
            Console.Write(element + " ");
        }
        Console.WriteLine();
    }
}

In the above code, we first find the maximum and minimum values ​​in the sequence to be sorted, and then create the auxiliary array count to Count the occurrences of each element. Next, the position of each element in the ordered sequence is obtained by performing a sum operation on the auxiliary array. Finally, based on the statistical results of the auxiliary array, the elements are put back into the original array to complete the sorting.

In the test code, we use a sample array to test the counting sort algorithm. The output shows the original array and the sorted results.

Through the above code examples, we can understand how to implement the counting sorting algorithm in C#. Counting sort is a simple but effective sorting algorithm, especially suitable for situations where the range of elements in the sequence to be sorted is small. By mastering the principles and implementation of counting sorting algorithms, we can choose the most suitable sorting algorithm when sorting is needed and improve the efficiency of the program.

The above is the detailed content of How to implement counting sorting algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!