C# 中的希尔排序程序
csharpprogrammingserver side programming更新于 2025/9/13 22:22:17
希尔排序允许交换数组中相距较远的元素，然后缩小它们之间的距离。这是插入排序的一种推广。希尔排序之所以如此著名，是因为它是由唐纳德·希尔 (Donald Shell) 首次提出的。
以下是使用 C# 演示希尔排序的程序 −
示例
using System;
namespace ShellSortDemo {
public class Example {
static void shellSort(int[] arr, int n) {
int i, j, pos, temp;
pos = 3;
while (pos > 0) {
for (i = 0; i < n; i++) {
j = i;
temp = arr[i];
while ((j >= pos) && (arr[j - pos] > temp)) {
arr[j] = arr[j - pos];
j = j - pos;
}
arr[j] = temp;
}
if (pos / 2 != 0)
pos = pos / 2;
else if (pos == 1)
pos = 0;
else
pos = 1;
}
}
static void Main(string[] args) {
int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
int i;
Console.WriteLine("Shell Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
shellSort(arr, n);
Console.Write("
Sorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}
输出
上述程序的输出如下。
Shell Sort Initial array is: 56 12 99 32 1 95 25 5 100 84 Sorted Array is: 1 5 12 25 32 56 84 95 99 100
现在让我们理解一下上面的程序。
在 main() 函数中，首先显示初始数组。然后，调用函数 shellSort() 对数组进行希尔排序。此代码片段如下所示 −
int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
int n = arr.Length;
int i;
Console.WriteLine("Shell Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
shellSort(arr, n);
在函数 shellSort() 中，使用 while 循环和 for 循环对给定数组进行排序。希尔排序的间隔为 3。代码片段如下。
static void shellSort(int[] arr, int n) {
int i, j, pos, temp;
pos = 3;
while (pos > 0) {
for (i = 0; i < n; i++) {
j = i;
temp = arr[i];
while ((j >= pos) && (arr[j - pos] > temp)) {
arr[j] = arr[j - pos];
j = j - pos;
}
arr[j] = temp;
}
if (pos / 2 != 0)
pos = pos / 2;
else if (pos == 1)
pos = 0;
else
pos = 1;
}
}
