如何实现C#中的计数排序算法
计数排序是一种简单但有效的排序算法,它可以在O(n+k)的时间复杂度下对一组整数进行排序,其中n是待排序的元素个数,k是待排序的元素范围。
计数排序的基本思想是创建一个辅助数组,用来统计待排序序列中每个元素的出现次数。然后,通过对辅助数组进行求和操作,得到每个元素在有序序列中的位置。最后,根据辅助数组的统计结果,将元素放回原始数组中,完成排序。
下面是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();
}
}
以上代码中,我们首先找到待排序序列中的最大值和最小值,然后创建辅助数组count来统计每个元素的出现次数。接下来,通过对辅助数组进行求和操作,得到每个元素在有序序列中的位置。最后,根据辅助数组的统计结果,将元素放回原始数组中,完成排序。
在测试代码中,我们使用一个示例数组来测试计数排序算法。输出结果显示原始数组和排序结果。
通过以上代码示例,我们可以了解到C#中如何实现计数排序算法。计数排序是一种简单但有效的排序算法,尤其适用于待排序序列中元素范围较小的情况。通过掌握计数排序算法的原理和实现方式,我们可以在需要排序的时候选择最适合的排序算法,提高程序的效率。