希尔排序--改良版插入排序
不论你在什么时候开始，重要的是开始之后就不要停止；不论你在什么时候结束，重要的是结束之后就不要悔恨。
Part 1
算法背景
插入排序法本质上是由未排序的后半部前端取出一个值，插入已排序前半部的适当位置。总的来说，概念简单但速度不快。
加快排序效率，基本原则之一就是让后一次的排序进行时，尽量利用前一次排序后的结果。希尔排序（Shell排序法）即是基于此一概念来改良插入排序法。
Part 2
算法解析
希尔排序样例
解法：假设要排序的元素有n个，则每次进行插入排序时并不是所有的元素同时进行时，而是取一段间隔。
对数据11 2 10 8 16 33进行希尔排序步骤如下：
第一次排序间隔：6 / 2 = 3
第一次排序结果：8 2 10 11 16 33
第二次排序间隔：3 / 2 = 1
第二次排序结果：2 8 10 11 16 33
最终经过二次插入排序，生成的结果为2 8 10 11 16 33.相较于常规的插入排序算法，效率有了很大的提升。
Part 3
算法实现
public class ShellSort {
void sort(int number[]) {
int Max = number.length;
int gap = Max / 2;
while (gap > 0) {
for (int kk = 0; kk < gap; kk++) {
for (int ii = kk + gap; ii < Max; ii += gap) {
for (int jj = ii - gap; jj >= kk; jj -= gap) {
if (number[jj] > number[jj + gap]) {
int temp;
temp = number[jj + gap];
number[jj + gap] = number[jj];
number[jj] = temp;
} else {
break;
}
}
}
}
System.out.println("gap = " + gap);
for (int ii = 0; ii < Max; ii++) {
System.out.print(number[ii] + " ");
}
System.out.println();
gap /= 2;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入待排序的数据(例如:11 2 10 8 16 33):");
String input = scanner.nextLine();
scanner.close();
String[] str = input.split(" ");
int number[] = new int[str.length];
for (int i = 0; i < number.length; i++) {
number[i] = Integer.parseInt(str[i]);
}
ShellSort shellSort = new ShellSort();
shellSort.sort(number);
}
}运行结果：
往期精彩回顾
长按二维码识别关注