C# 希尔排序算法
最后修改于 2025年3月8日
本教程介绍了 C# 中的希尔排序算法，演示了如何使用它对数字和文本数据进行升序和降序排序，并与快速排序进行了基准测试。
算法是为了高效解决问题或执行任务而精心设计的一系列明确定义的步骤。它是编程的支柱，能够提供系统化的解决方案。
排序是将数据排列成特定顺序（例如升序或降序）的行为。它对于优化各种应用程序中的数据访问和分析至关重要。
常用排序算法
以下是一些常用的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- Shell Sort（希尔排序）
Shell Sort 算法
希尔排序通过比较和排序特定间隔或间隙的元素来增强插入排序，而不是相邻的元素。 它从较大的间隙开始，并在迭代过程中减小它们。
这种方法最大限度地减少了所需的移位次数，使其比普通插入排序更有效。 其时间复杂度在 O(n log n) 和 O(n²) 之间变化，具体取决于间隙序列。
Shell Sort 示例
这是使用顶级语句的 C# 希尔排序的数字数据实现。
// ShellSort.cs
void ShellSort(int[] arr)
{
int n = arr.Length;
int gap = n / 2;
for (; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i++)
{
int temp = arr[i];
int j = i;
for (; j >= gap && arr[j - gap] > temp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int[] nums = [12, 34, 54, 2, 3];
ShellSort(nums);
Console.WriteLine("Sorted array: " + string.Join(" ", nums));
ShellSort 方法按升序对整数数组进行排序。 它从数组长度的一半的间隙开始，每次迭代将其缩小一半。
在每个间隙内，它执行类似插入的排序，将较大的元素向右移动。 此示例对一个小数组进行排序，显示了该算法在 C# 中的基本操作。
对文本数据进行排序
希尔排序也可以对字符串进行排序。 下面是一个 C# 中升序和降序的示例。
// ShellSortText.cs
void ShellSort(string[] arr, bool reverse)
{
int n = arr.Length;
int gap = n / 2;
for (; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i++)
{
string temp = arr[i];
int j = i;
if (reverse)
{
for (; j >= gap && arr[j - gap] < temp; j -= gap)
{
arr[j] = arr[j - gap];
}
}
else
{
for (; j >= gap && arr[j - gap] > temp; j -= gap)
{
arr[j] = arr[j - gap];
}
}
arr[j] = temp;
}
}
}
string[] words = ["apple", "banana", "cherry", "date", "elderberry"];
ShellSort(words, false);
Console.WriteLine("Ascending order: " + string.Join(" ", words));
ShellSort(words, true);
Console.WriteLine("Descending order: " + string.Join(" ", words));
ShellSort 方法现在接受一个 reverse 布尔值来切换排序方向。 对于升序，它移动较大的字符串；对于降序，它移动较小的字符串。
这会在适当位置对字符串数组进行排序，使其在 C# 程序中可用于文本数据（如名称或类别），基于间隙的方法提高了效率。
Shell Sort 与 Quick Sort 的比较
希尔排序为中等大小的数据提供了良好的性能，但快速排序的平均 O(n log n) 复杂度通常使其在大型数据集上更快。 此基准测试在 C# 中比较了它们。
// CompareSorts.cs
using System.Diagnostics;
void ShellSort(int[] arr)
{
int n = arr.Length;
int gap = n / 2;
for (; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i++)
{
int temp = arr[i];
int j = i;
for (; j >= gap && arr[j - gap] > temp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
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[10000];
for (int i = 0; i < data.Length; i++)
{
data[i] = rand.Next(1000);
}
int[] shellData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
ShellSort(shellData);
double shellTime = sw.Elapsed.TotalSeconds;
int[] quickData = data.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Shell Sort time: {shellTime:F6} seconds");
Console.WriteLine($"Quick Sort time: {quickTime:F6} seconds");
此基准测试在 10,000 个随机整数上测试这两种算法。 希尔排序使用间隙在适当位置修改数组，而快速排序通过递归创建新数组。
由于其分而治之的效率，快速排序通常优于大型数据集上的希尔排序。 希尔排序在较小或部分排序的数据上表现出色，提供了一种实用的权衡。
了解这些差异有助于在 C# 中为特定用例选择最佳算法，从而平衡简单性和速度。
来源
本教程介绍了 C# 中的希尔排序，其中包含数字和文本的示例，以及与快速排序的性能比较。
作者
列出所有 C# 教程。