希爾排序簡介

• 希爾排序（shell sort）選定一個小于N（數列長度）的整數gap作為第一增量，然后將所有距離為gap的元素分成一組，然后對每一組的元素進行插入排序。
• 然后再取一個比前一個增量小的整數作為增量，重復上面的步驟操作…
• 當增量大小減少到1時候，就相當于對整個序列再進行一次插入排序，然后排序完成。

代碼實現

package com.xxliao.algorithms.sort.shell_sort;/*** @author xxliao* @description: 希爾排序* @date 2024/5/30 21:44*/
public class ShellSort {public static void main(String[] args) {int[] array = {1,6,2,6,8,3,8,3,9,3,4,6,56,8};System.out.print("排序前：");printArray(array);sort(array);System.out.print("排序后：");printArray(array);}/*** @description  希爾排序* @author  xxliao* @date  2024/5/30 21:46*/public static void sort(int[] array) {// 定義gap,初始等于lengthint gap = array.length;while(gap > 1) {gap = gap / 2;// 單次gap排序for (int i = 0; i < array.length - gap; i++) {int end = i;int nextItem = array[end+gap];while(end >= 0) {if(array[end] > nextItem) {// 前面的值比后面大,換到后面位置去array[end+gap] = array[end];end = end - gap;// end小于gap時候是退出里層循環，end大于gap的時候是進行下一次的輪詢}else {// 前面的值小于等于后面的值，不用替換break;}}array[end+gap] = nextItem;}}}/*** @description  打印數組* @author  xxliao* @date  2024/5/30 21:47*/public static void printArray(int[] array) {for (int i = 0; i <= array.length - 1; i++) {System.out.print(array[i]+" ");}System.out.println();}
}

演示結果：