C#希尔排序算法

以下是C#实现的希尔排序算法的详细说明与代码示例：

希尔排序核心原理

希尔排序通过分组插入排序和动态调整间隔实现高效排序：

分组阶段：选择初始间隔（通常为数组长度的一半），将数组划分为多个子序列。
子序列排序：对每个子序列执行插入排序，缩小逆序对距离。
间隔收缩：逐步缩小间隔（如每次减半），重复分组和排序过程，直至间隔为1完成最终排序。

动态演示：初始间隔较大时快速定位大范围逆序，间隔缩小后精细调整局部顺序完整代码实现public static void ShellSort(int[] array){ int arrLength = array.Length; int gap = arrLength / 2; // 初始间隔设为数组长度一半 while (gap > 0) { // 对每个子序列进行插入排序 for (int i = gap; i < arrLength; i++) { int temp = array[i]; int j = i; // 子序列内部插入排序：比较并移动元素 while (j >= gap && array[j - gap] > temp) { array[j] = array[j - gap]; j -= gap; } array[j] = temp; // 插入元素到正确位置 } gap /= 2; // 缩小间隔 }}// 测试方法public static void ShellSortRun(){ int[] array = { 19, 20, 22, 32, 34, 50, 99, 49, 1, 11, 11, 55, 35, 93, 96, 71, 70, 38, 78, 48 }; Console.WriteLine("排序前数组：" + string.Join(", ", array)); ShellSort(array); Console.WriteLine("排序后数组：" + string.Join(", ", array));}关键点解析

间隔选择策略：示例中使用gap /= 2的简单收缩方式，实际可优化为Hibbard序列（如1, 3, 7, 15...）或Sedgewick序列，以获得更优的时间复杂度（最坏情况下从O(n2)降至O(n^(3/2))）。
子序列排序逻辑：
外层循环for (int i = gap; i < arrLength; i++)遍历所有子序列元素。
内层while循环通过比较array[j - gap]与temp，实现子序列内部的插入排序，确保每次将较大元素向后移动。
稳定性与适应性：
希尔排序是不稳定排序（相同元素可能因间隔调整改变相对位置）。
对部分有序数组效率显著高于普通插入排序，适合中等规模数据。

运行结果验证

执行ShellSortRun()方法输出：

排序前数组：19, 20, 22, 32, 34, 50, 99, 49, 1, 11, 11, 55, 35, 93, 96, 71, 70, 38, 78, 48 排序后数组：1, 11, 11, 19, 20, 22, 32, 34, 35, 38, 48, 49, 50, 55, 70, 71, 78, 93, 96, 99 验证结果：数组已按升序排列，符合预期优化建议

间隔序列优化：替换为gap = 3 * gap + 1（Sedgewick序列）可提升性能。
并行化处理：对大规模数据，可并行处理不同子序列的排序阶段。
混合排序：结合快速排序或堆排序，对小规模子序列使用插入排序进一步优化。

此实现完整展示了希尔排序的核心逻辑，可直接用于教学或中小规模数据排序场景。

您可能感兴趣问答

Collapsible

热门标签

热点问答