C# 冒泡排序
最后修改于 2025年3月8日
本教程探讨了 C# 中的冒泡排序算法。我们将演示如何按升序和降序对数值和文本数据进行排序，并将其与快速排序进行基准测试。
算法 是一个定义明确的步骤序列，旨在高效地解决问题或完成任务。在编程中，算法是计算逻辑的支柱。
排序 指的是将数据集合组织成特定的序列，例如升序（从小到大）或降序（从大到小）。它是许多应用中的关键操作，从数据库到用户界面。
常用排序算法
以下是一些广泛认可的排序算法：
- 气泡排序
- 快速排序
- 归并排序
- 插入排序
- 选择排序
气泡排序算法
冒泡排序是一种简单的排序方法，它遍历列表，比较相邻的项目，如果它们顺序错误则交换它们。之所以这样命名，是因为较大的元素如何“冒泡”到末尾。
该过程重复进行，直到不再需要交换，表明列表已排序。虽然简单，但由于其二次时间复杂度，对于大型数据集来说不是最快的。
气泡排序示例
下面是使用顶级语句和隐式 using 的数字冒泡排序的 C# 实现。
// BubbleSort.cs
void BubbleSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}
}
}
}
int[] nums = [64, 34, 25, 12, 22, 11, 90];
BubbleSort(nums);
Console.WriteLine("Sorted array: " + string.Join(" ", nums));
此代码定义了一个 BubbleSort 方法，该方法按升序对整数数组进行排序。外循环运行 n 次，其中 n 是数组的长度。
内循环比较相邻的元素，如果左侧大于右侧，则交换它们。执行后，数组将按从小到大的顺序排序。
对文本数据进行排序
冒泡排序也可以处理字符串。这是一个按升序和降序对文本进行排序的示例。
// BubbleSortText.cs
void BubbleSort(string[] arr, bool reverse)
{
int n = arr.Length;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
int cmp = string.Compare(arr[j], arr[j + 1]);
if ((!reverse && cmp > 0) || (reverse && cmp < 0))
{
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}
}
}
}
string[] words = ["banana", "apple", "cherry", "date"];
BubbleSort(words, false);
Console.WriteLine("Ascending order: " + string.Join(" ", words));
BubbleSort(words, true);
Console.WriteLine("Descending order: " + string.Join(" ", words));
BubbleSort 方法现在接受一个 reverse 布尔值来切换排序方向。对于升序，如果左侧字符串按字母顺序大于右侧字符串，则交换它们。
对于降序，如果左侧小于右侧，则交换它们。这种灵活性使其可用于在 C# 程序中对名称、标签或其他文本数据进行排序。
比较气泡排序与快速排序
冒泡排序的简单性是有代价的——对于大型数据集来说，它很慢，时间复杂度为 O(n²)。快速排序的平均复杂度为 O(n log n)，速度更快。
下面的示例使用大型随机数据集对两种算法进行基准测试，以突出它们在 C# 中的性能差异。
using System.Diagnostics;
// SortBenchmark.cs
void BubbleSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}
}
}
}
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[5000];
for (int i = 0; i < data.Length; i++)
{
data[i] = rand.Next(1000);
}
int[] bubbleData = (int[])data.Clone();
Stopwatch sw = Stopwatch.StartNew();
BubbleSort(bubbleData);
double bubbleTime = sw.Elapsed.TotalSeconds;
int[] quickData = (int[])data.Clone();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Bubble Sort time: {bubbleTime:F6} seconds");
Console.WriteLine($"Quick Sort time: {quickTime:F6} seconds");
此代码生成 1000 个随机整数并计时两种排序方法。 BubbleSort 方法就地修改数组，而 QuickSort 使用递归返回一个新的已排序数组。
快速排序围绕一个枢轴对数据进行分区，递归地对子列表进行排序，使其更有效。基准测试通常表明冒泡排序花费的时间明显更长——通常是 10 倍或更多。
了解这些差异有助于开发人员为他们的需求选择正确的算法，从而在实际的 C# 应用程序中平衡简单性和性能。
来源
本教程介绍了 C# 中的冒泡排序，其中包含数字和文本的示例，以及与快速排序的性能比较。
作者
列出所有 C# 教程。