# 2.4 希尔排序（Shell Sort） #### 一. 定义 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为\*\*缩小增量排序\*\*，是突破O(n\^2\^)的第一批算法。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 !\[图片4\](https://hgh-typora-image.oss-cn-guangzhou.aliyuncs.com/img/%E5%9B%BE%E7%89%874.png) #### 二. 代码实现 \`\`\`java /\*\* \* 希尔排序 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-12-16:42 \*\*/ public class ShellSort { public static void main(String\[\] args) { int\[\] arr = {8,9,1,7,2,3,5,4,6,0}; shellSort(arr); } //希尔排序：在插入时采用交换法 public static void shellSort(int\[\] arr){ int temp = 0; int count = 0; for(int gap = arr.length/2; gap \> 0; gap /=2){ for(int i = gap; i \< arr.length; i++){ //遍历各组中的所有元素（共gap组，每组有arr.length/gap个元素），步长为gap for(int j = i - gap; j \>= 0; j -= gap){ //如果当前元素大于加上步长后的那个元素，说明交换 if(arr\[j\] \> arr\[j + gap\]){ temp = arr\[j\]; arr\[j\] = arr\[j + gap\]; arr\[j + gap\] = temp; } } } System.out.println("希尔排序第" + (++count) + "轮 = " + Arrays.toString(arr)); } } } \`\`\`