GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — algorithms/sorting/shellsort/ShellSort.java at main · microwind/algorithms Expand file tree/ Copy pathShellSort.javaMore file actions 358 lines (307 loc) · 12.6 KB / Copy pathShellSort.javaFile metadata and controls358 lines (307 loc) · 12.6 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 /** * Copyright © https://github.com/microwind All rights reserved. * * @author: [email protected] * @version: 1.0 */ /** * 希尔排序算法实现 * 提供四种不同的实现方式，适合不同场景和性能需求 */ import java.util.Arrays; public class ShellSort { /** * 打印数组内容的辅助函数 */ private static void printArray(int[] arr, String label) { System.out.println(label + ": " + Arrays.toString(arr)); } /** * 性能测试辅助函数 */ private static void performanceTest(SortFunction sortFunc, int[] arr, String name) { // 创建数组副本，避免修改原数组 int[] testArr = Arrays.copyOf(arr, arr.length); printArray(testArr, name + "原始数组"); // 开始计时 long startTime = System.nanoTime(); sortFunc.sort(testArr); long endTime = System.nanoTime(); System.out.println(name + ": " + String.format("%.3f", (endTime - startTime) / 1_000_000.0) + "ms"); printArray(testArr, name + "排序结果"); System.out.println(); // 空行分隔 } // ==================== 主程序：算法演示和性能测试 ==================== // 测试数据：包含大数字和负数的典型数组 private static final int[] testData = {33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431}; /** * 希尔排序基础版本 - 原始Shell序列 * * 算法原理： * 1. 选择一个增量序列，如 n/2, n/4, ..., 1 * 2. 对每个增量进行插入排序，但只比较相距增量的元素 * 3. 逐步减小增量，直到增量为1，此时数组基本有序 * 4. 最后一次插入排序完成整个排序过程 * * 生活类比：就像整理一副扑克牌，先按间隔几张牌进行分组整理， * 然后逐步缩小间隔，最后对相邻的牌进行精细整理 * * 时间复杂度：平均O(n^1.3)，最坏O(n^2)，取决于增量序列 * 空间复杂度：O(1) - 原地排序 * 稳定性：不稳定 - 相距增量的元素交换可能改变相等元素的相对位置 */ public static void shellSort1(int[] arr) { System.out.println("shellSort1 original sequence:"); int n = arr.length; // 原始Shell序列：n/2, n/4, ..., 1 for (int gap = n / 2; gap > 0; gap /= 2) { // 对每个增量进行插入排序 for (int i = gap; i < n; i++) { // 关键点：保存当前元素，与前面相距gap的元素比较 int temp = arr[i]; int j = i; // 向前查找插入位置 while (j >= gap && arr[j - gap] > temp) { System.out.println("gap=" + gap + " i=" + i + " j-gap=" + (j - gap) + " j=" + j + " arr:" + java.util.Arrays.toString(arr)); arr[j] = arr[j - gap]; j -= gap; } // 插入元素 arr[j] = temp; } } printArray(arr, "排序后数组"); } /** * 希尔排序优化版本 - Knuth序列 * * 算法思路： * 使用Knuth提出的增量序列：1, 4, 13, 40, ... * 公式：gap = 3 * gap + 1，然后反向递减 * * 优化效果： * - 更好的增量序列，减少比较次数 * - 理论上更优的时间复杂度 * * 时间复杂度：平均O(n^1.25)，比原始序列更优 * 空间复杂度：O(1) - 原地排序 * 稳定性：不稳定 - 插入排序的不稳定性继承 */ public static void shellSort2(int[] arr) { System.out.println("shellSort2 Knuth sequence:"); int n = arr.length; // 计算初始增量（Knuth序列） int gap = 1; while (gap < n / 3) { gap = 3 * gap + 1; // 1, 4, 13, 40, 121, ... } // 反向递减处理 for (; gap > 0; gap /= 3) { // 对每个增量进行插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i - gap; // 向前查找插入位置 for (; j >= 0 && arr[j] > temp; j -= gap) { System.out.println("gap=" + gap + " i=" + i + " j=" + j + " j+gap=" + (j + gap) + " arr:" + java.util.Arrays.toString(arr)); arr[j + gap] = arr[j]; } arr[j + gap] = temp; } } printArray(arr, "排序后数组"); } /** * 希尔排序 - Hibbard序列 * * 算法思路： * 使用Hibbard序列：1, 3, 7, 15, 31, ... * 公式：gap = 2^k - 1 * * 优化效果： * - 更好的增量分布 * 理论时间复杂度为O(n^(3/2)) * * 时间复杂度：平均O(n^1.5) * 空间复杂度：O(1) - 原地排序 * 稳定性：不稳定 - 插入排序的不稳定性继承 */ public static void shellSort3(int[] arr) { System.out.println("shellSort3 Hibbard sequence:"); int n = arr.length; // 生成Hibbard序列 java.util.List<Integer> gaps = new java.util.ArrayList<>(); int k = 1; while ((Math.pow(2, k) - 1) < n) { gaps.add((int) (Math.pow(2, k) - 1)); k++; } // 反向使用序列 for (int g = gaps.size() - 1; g >= 0; g--) { int gap = gaps.get(g); // 对每个增量进行插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j; // 向前查找插入位置 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } printArray(arr, "排序后数组"); } /** * 希尔排序 - Sedgewick序列 * * 算法思路： * 使用Sedgewick序列：1, 5, 19, 41, 109, ... * 结合4^k + 3*2^(k-1) + 1和9*2^k - 9*2^(k/2) + 1 * * 优化效果： * - 最优的增量序列之一 * - 更好的性能表现 * * 时间复杂度：平均O(n^1.25)，接近最优 * 空间复杂度：O(1) - 原地排序 * 稳定性：不稳定 - 插入排序的不稳定性继承 */ public static void shellSort4(int[] arr) { System.out.println("shellSort4 Sedgewick sequence:"); int n = arr.length; // 生成Sedgewick序列 java.util.List<Integer> gaps = new java.util.ArrayList<>(); // 使用简化版本：1, 5, 19, 41, 109, 209, 505, 929, 2161 int[] sedgewickGaps = {1, 5, 19, 41, 109, 209, 505, 929, 2161}; for (int gap : sedgewickGaps) { if (gap < n) { gaps.add(gap); } } // 反向使用序列 for (int g = gaps.size() - 1; g >= 0; g--) { int gap = gaps.get(g); // 对每个增量进行插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j; // 向前查找插入位置 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } /** * 希尔排序 - 递归版本（尾递归实现） * * 算法思路： * 递归处理增量（分组）序列，每个增量插入排序 * 增量序列采用 gap/2（希尔原始序列） * * 递归结构： * - 外层尾递归：处理递减的增量序列 * - 内层循环：对每个位置进行插入排序 */ /** * 递归希尔排序版 - 尾递归实现 * * @param arr 待排序数组 * @param gap 当前增量 */ public static void shellSort5(int[] arr, int gap) { // 递归终止条件 if (gap <= 0) { return; } // 对当前增量（分组）进行插入排序 for (int i = gap; i < arr.length; i++) { int temp = arr[i]; int j = i; // 向前查找插入位置 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } // 插入到对应位置 arr[j] = temp; } // 尾递归调用：递归是函数的最后操作 shellSort5(arr, gap / 2); } // ==================== 算法测试和性能对比 ==================== @FunctionalInterface private interface SortFunction { void sort(int[] arr); } public static void main(String[] args) { // 测试1：原始Shell序列 performanceTest(ShellSort::shellSort1, testData, "原始Shell序列"); // 测试2：Knuth序列 performanceTest(ShellSort::shellSort2, testData, "Knuth序列"); // 测试3：Hibbard序列 performanceTest(ShellSort::shellSort3, testData, "Hibbard序列"); // 测试4：Sedgewick序列 performanceTest(ShellSort::shellSort4, testData, "Sedgewick序列"); // 测试5：递归版本 performanceTest(arr -> { shellSort5(arr, arr.length / 2); }, testData, "递归版本"); System.out.println("=== 算法对比总结 ==="); System.out.println("1. 原始Shell序列：简单实现，易于理解"); System.out.println("2. Knuth序列：经典优化，性能提升"); System.out.println("3. Hibbard序列：数学优化，理论更优"); System.out.println("4. Sedgewick序列：最优序列，性能最佳"); System.out.println("5. 递归版本：尾递归优化实现"); } } /* 打印结果 jarry@Mac shellsort % java ShellSort.java 原始Shell序列原始数组: [33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] shellSort1 original sequence: gap=5 i=5 j-gap=0 j=5 arr:[33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] gap=5 i=9 j-gap=4 j=9 arr:[-7, 4, 15, 43, 323454, 33, 105, 1235, 200, 87431] gap=2 i=5 j-gap=3 j=5 arr:[-7, 4, 15, 43, 87431, 33, 105, 1235, 200, 323454] gap=2 i=6 j-gap=4 j=6 arr:[-7, 4, 15, 33, 87431, 43, 105, 1235, 200, 323454] gap=2 i=8 j-gap=6 j=8 arr:[-7, 4, 15, 33, 105, 43, 87431, 1235, 200, 323454] gap=1 i=5 j-gap=4 j=5 arr:[-7, 4, 15, 33, 105, 43, 200, 1235, 87431, 323454] 排序后数组: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] 原始Shell序列: 2.780ms 原始Shell序列排序结果: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] Knuth序列原始数组: [33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] shellSort2 Knuth sequence: gap=4 i=5 j=1 j+gap=5 arr:[33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] gap=4 i=8 j=4 j+gap=8 arr:[33, -7, 15, 43, 323454, 4, 105, 1235, 200, 87431] gap=1 i=1 j=0 j+gap=1 arr:[33, -7, 15, 43, 200, 4, 105, 1235, 323454, 87431] gap=1 i=2 j=1 j+gap=2 arr:[-7, 33, 15, 43, 200, 4, 105, 1235, 323454, 87431] gap=1 i=5 j=4 j+gap=5 arr:[-7, 15, 33, 43, 200, 4, 105, 1235, 323454, 87431] gap=1 i=5 j=3 j+gap=4 arr:[-7, 15, 33, 43, 200, 200, 105, 1235, 323454, 87431] gap=1 i=5 j=2 j+gap=3 arr:[-7, 15, 33, 43, 43, 200, 105, 1235, 323454, 87431] gap=1 i=5 j=1 j+gap=2 arr:[-7, 15, 33, 33, 43, 200, 105, 1235, 323454, 87431] gap=1 i=6 j=5 j+gap=6 arr:[-7, 4, 15, 33, 43, 200, 105, 1235, 323454, 87431] gap=1 i=9 j=8 j+gap=9 arr:[-7, 4, 15, 33, 43, 105, 200, 1235, 323454, 87431] 排序后数组: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] Knuth序列: 0.230ms Knuth序列排序结果: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] Hibbard序列原始数组: [33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] shellSort3 Hibbard sequence: 排序后数组: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] Hibbard序列: 0.074ms Hibbard序列排序结果: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] Sedgewick序列原始数组: [33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] shellSort4 Sedgewick sequence: Sedgewick序列: 0.009ms Sedgewick序列排序结果: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] 递归版本原始数组: [33, 4, 15, 43, 323454, -7, 105, 1235, 200, 87431] 递归版本: 0.002ms 递归版本排序结果: [-7, 4, 15, 33, 43, 105, 200, 1235, 87431, 323454] === 算法对比总结 === 1. 原始Shell序列：简单实现，易于理解 2. Knuth序列：经典优化，性能提升 3. Hibbard序列：数学优化，理论更优 4. Sedgewick序列：最优序列，性能最佳 5. 递归版本：尾递归优化实现 */ |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |