C# 插入排序
最后修改于 2025年3月8日
本教程解释了 C# 中的插入排序算法，展示了它在升序和降序中对数值和文本数据的应用，以及与快速排序的基准测试。
算法 是为有效解决问题或完成任务而设计的一组精确步骤。它是编程中的一个核心概念，能够进行数据处理和自动化。
排序 涉及将数据排列成定义的顺序，例如升序或降序。它对于优化数据检索和支持分析任务至关重要。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
插入排序
插入排序 是一种简单的算法，它以递增的方式构建已排序的数组，一次一个元素。 对于小型或几乎已排序的数据集，它非常有效。
时间复杂度为 O(n²)，对于大型数据集来说效率低下，但它的简单性和原地操作使其对于在线排序等特定用例很有价值。
插入排序示例
这是使用顶层语句实现的 C# 数字和字符串插入排序。
// InsertionSort.cs
void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] > key; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
void InsertionSortStrings(string[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
string key = arr[i];
int j = i - 1;
for (; j >= 0 && string.Compare(arr[j], key) > 0; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
void InsertionSortDesc(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] < key; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
void InsertionSortStringsDesc(string[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
string key = arr[i];
int j = i - 1;
for (; j >= 0 && string.Compare(arr[j], key) < 0; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
int[] numbers = [12, 11, 13, 5, 6];
string[] words = ["apple", "banana", "cherry", "date"];
InsertionSort(numbers);
Console.WriteLine("Sorted numbers (ascending): " + string.Join(" ", numbers));
InsertionSortStrings(words);
Console.WriteLine("Sorted words (ascending): " + string.Join(" ", words));
InsertionSortDesc(numbers);
Console.WriteLine("Sorted numbers (descending): " + string.Join(" ", numbers));
InsertionSort-stringsDesc(words);
Console.WriteLine("Sorted words (descending): " + string.Join(" ", words));
InsertionSort 和 InsertionSortStrings 方法按升序对整数和字符串进行排序，而 InsertionSortDesc 和 InsertionSortStringsDesc 按降序排序。
每个方法都在原地工作，移动元素以将当前键插入到其正确的位置。这展示了 C# 的类型特定方法，可以有效地处理数值和文本数据。
说明
插入排序迭代数组，将第一个元素视为已排序。对于每个后续元素，它会将较大的元素（降序时为较小的元素）向右移动。
// InsertionSort method
void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] > key; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
InsertionSort 方法通过将每个键与先前的元素进行比较来按升序排序，根据需要进行移动直到键适合为止。
// InsertionSortDesc method
void InsertionSortDesc(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] < key; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
InsertionSortDesc 方法反转比较以按降序排序，移动较小的元素以为键腾出空间。
插入排序与快速排序的比较
插入排序的 O(n²) 复杂度适用于小型或部分排序的数据，而快速排序的平均 O(n log n) 效率在较大数据集上表现出色。 此基准测试突出了它们在 C# 中的差异。
// Benchmark.cs
using System.Diagnostics;
void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int key = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] > key; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = key;
}
}
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);
}
int[] insertData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
InsertionSort(insertData);
double insertTime = sw.Elapsed.TotalSeconds;
int[] quickData = data.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Insertion Sort Time: {insertTime:F6} seconds");
Console.WriteLine($"Quick Sort Time: {quickTime:F6} seconds");
此基准测试在 1,000 个随机整数上测试两种算法。 插入排序在原地修改数组，而快速排序通过递归和分区创建新数组。
由于其对数缩放，快速排序通常在较大数据集上明显优于插入排序。 插入排序的优势在于它的简单性和在小型或几乎排序的数据上的性能。
来源
本教程解释了 C# 中的插入排序，并提供了数字和文本的示例，以及与快速排序的基准测试。
作者
列出所有 C# 教程。