ZetCode

C# 选择排序

最后修改于 2025 年 3 月 9 日

本文探讨了 C# 中的选择排序算法。我们将定义它，展示数字和字符串排序的示例，并将其与快速排序进行比较。

算法是解决问题或完成任务的清晰、循序渐进的过程。 它是编程中的核心概念，指导代码如何工作。

排序将数据组织成特定的顺序，例如升序或降序。 它是计算机科学中用于管理和访问数据的关键技能。

常用排序算法

以下是一些常用的排序算法

选择排序算法

选择排序算法重复扫描列表的未排序部分，以找到最小（或最大）的元素。 然后，它将此元素与第一个未排序的位置交换。

重复此过程，直到列表完全排序。 它易于理解和实现，但对于大型数据集来说不是最快的。

选择排序示例

下面是选择排序的 C# 实现。 它适用于数组，并且可以按升序或降序排序。

SelectionSort.cs 
// SelectionSort.cs
T[] SelectionSort<T>(T[] arr, bool ascending)
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        int idx = i;
        for (int j = i + 1; j < n; j++)
        {
            int comparison = Comparer<T>.Default.Compare(arr[j], arr[idx]);
            if ((ascending && comparison < 0) || (!ascending && comparison > 0))
            {
                idx = j;
            }
        }
        if (idx != i)
        {
            (arr[i], arr[idx]) = (arr[idx], arr[i]);
        }
    }
    return arr;
}

int[] numbers = [64, 25, 12, 22, 11];
string[] words = ["apple", "banana", "kiwi", "cherry"];

Console.WriteLine("Ascending: " + string.Join(" ", SelectionSort(numbers, true)));
Console.WriteLine("Descending: " + string.Join(" ", SelectionSort(numbers, false)));
Console.WriteLine("Ascending: " + string.Join(" ", SelectionSort(words, true)));
Console.WriteLine("Descending: " + string.Join(" ", SelectionSort(words, false)));

SelectionSort 方法接受一个类型为 T 的数组和一个用于排序方向的布尔值。 它使用 Comparer.Default 来处理不同的数据类型，例如整数和字符串。

选择排序与快速排序的比较

选择排序很容易编写代码，但对于大型列表来说速度很慢，时间复杂度为 O(n²)。 快速排序使用分而治之的策略，平均速度更快，为 O(n log n)。 让我们对它们进行基准测试。

Benchmark.cs 
// Benchmark.cs
using System.Diagnostics;

int[] SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n; i++)
    {
        int idx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[idx])
            {
                idx = j;
            }
        }
        if (idx != i)
        {
            (arr[i], arr[idx]) = (arr[idx], arr[i]);
        }
    }
    return arr;
}

int[] QuickSort(int[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }
    int pivot = arr[arr.Length / 2];
    var left = new List<int>();
    var middle = new List<int>();
    var right = new List<int>();
    foreach (int x in arr)
    {
        if (x < pivot)
        {
            left.Add(x);
        }
        else if (x == pivot)
        {
            middle.Add(x);
        }
        else
        {
            right.Add(x);
        }
    }
    return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}

Random rand = new(Random.Shared.Next());
int[] data = new int[1000];
for (int i = 0; i < data.Length; i++)
{
    data[i] = rand.Next(1000);
}

// Benchmark selection sort
int[] selectionData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
SelectionSort(selectionData);
Console.WriteLine($"Selection Sort Time: {sw.Elapsed.TotalSeconds:F6} seconds");

// Benchmark quick sort
int[] quickData = data.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
Console.WriteLine($"Quick Sort Time: {sw.Elapsed.TotalSeconds:F6} seconds");

此基准测试了 1000 个随机整数的选择排序和快速排序。 由于其高效的设计，快速排序通常完成得更快。

来源

C# 官方文档

本教程介绍了 C# 中的选择排序，并将其与快速排序进行了比较。

作者

我叫 Jan Bodnar，是一位充满热情的程序员，拥有多年的编程经验。 我自 2007 年以来一直在撰写编程文章。到目前为止，我已经撰写了 1400 多篇文章和 8 本电子书。 我在编程教学方面拥有超过八年的经验。

列出所有 C# 教程。