1、希尔排序
Shell Sort：是“插入排序算法”的一种更高效的改进版本。插入排序的一大问题是，当插入的数是一个较小数时，需要移动的次数明显增加；步骤：按数组下标的一定增量分组，对每组使用插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，最后进行一次插入排序后算法终止；稳定性：虽然单次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的；复杂度：O(n^(1.3—2))；分类：分为交换法希尔排序和移动法希尔排序，后者的运行效率明显比前者要高。
2、Java代码
package Algorithm.Sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author yhx
* @date 2020/10/04
*/
public class ShellSort {
private static final int NUM = 80000;
public static void main(String[] args) {
//定义待排序数组
int[] arr1 = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
int[] arr2 = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
int[] arr3 = new int[NUM];
int[] arr4 = new int[NUM];
for (int i = 0; i < NUM; i++) {
// .random()用于产生一个0到1的随机小数
arr3[i] = (int) ((Math.random() * 2 - 1) * NUM);
arr4[i] = (int) ((Math.random() * 2 - 1) * NUM);
}
System.out.println("希尔排序步骤详解：");
Shell shell = new Shell();
shell.shellProcess(arr1);
System.out.println();
System.out.println("整合后的希尔排序：");
shell.shellExchange(arr2);
System.out.println("整合后的希尔排序 arr2[] = " + Arrays.toString(arr2));
System.out.println();
// 希尔排序前（交换法）
System.out.println("测试希尔排序（交换法）的运行时长：");
// 时间标记精确到毫秒
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
// Date()函数用于标记时间
Date date1 = new Date();
String date1Str = simpleDateFormat.format(date1);
System.out.println("arr3[]希尔排序前（交换法）的时间是：" + date1Str);
shell.shellExchange(arr3);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("arr3[]希尔排序后（交换法）的时间是：" + date2Str);
// 希尔排序前（移动法）
System.out.println("测试希尔排序（移动法）的运行时长：");
Date date3 = new Date();
String date3Str = simpleDateFormat.format(date3);
System.out.println("arr4[]希尔排序前（移动法）的时间是：" + date3Str);
shell.shellMove(arr4);
Date date4 = new Date();
String date4Str = simpleDateFormat.format(date4);
System.out.println("arr4[]希尔排序后（移动法）的时间是：" + date4Str);
//System.out.println("整合后的希尔排序 arr3[] = " + Arrays.toString(arr3));
//System.out.println("整合后的希尔排序 arr3[] = " + Arrays.toString(arr4));
}
}
class Shell {
/**
* 逐步推导希尔排序
*
* @param arr 待排序数组
*/
public void shellProcess(int[] arr) {
// 第一轮排序，将10个数据分为5组
int round = 10 / 2;
for (int i = round; i < arr.length; i++) {
for (int j = i - round; j >= 0; j -= round) {
if (arr[j] > arr[j + round]) {
int temp = arr[j];
arr[j] = arr[j + round];
arr[j + round] = temp;
}
}
}
System.out.println("第一轮希尔排序后 arr1[] = " + Arrays.toString(arr));
// 第二轮排序，将10个数据分为2组
round = round / 2;
for (int i = round; i < arr.length; i++) {
for (int j = i - round; j >= 0; j -= round) {
if (arr[j] > arr[j + round]) {
int temp = arr[j];
arr[j] = arr[j + round];
arr[j + round] = temp;
}
}
}
System.out.println("第二轮希尔排序后 arr1[] = " + Arrays.toString(arr));
// 第三轮排序，将10个数据分为1组
round = round / 2;
for (int i = round; i < arr.length; i++) {
for (int j = i - round; j >= 0; j -= round) {
if (arr[j] > arr[j + round]) {
int temp = arr[j];
arr[j] = arr[j + round];
arr[j + round] = temp;
}
}
}
System.out.println("第三轮希尔排序后 arr1[] = " + Arrays.toString(arr));
}
/**
* 整合后的希尔排序_交换法
*
* @param arr 待排序树组
*/
public void shellExchange(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中的所有元素
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长后的那个元素，就交换位置
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
/**
* 整合后的希尔排序_移动法
* 移动法明显比交换法节约排序时间
*
* @param arr 待排序树组
*/
public void shellMove(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j - gap];
j -= gap;
}
// 当退出while循环，即找到了temp的插入位置
arr[j] = temp;
}
}
}
}
}
3、运行结果
希尔排序步骤详解：
第一轮希尔排序后 arr1[] = [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
第二轮希尔排序后 arr1[] = [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
第三轮希尔排序后 arr1[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
整合后的希尔排序：
整合后的希尔排序 arr2[] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
测试希尔排序（交换法）的运行时长：
arr3[]希尔排序前（交换法）的时间是：2020-10-04 10:49:20:470
arr3[]希尔排序后（交换法）的时间是：2020-10-04 10:49:26:698
测试希尔排序（移动法）的运行时长：
arr4[]希尔排序前（移动法）的时间是：2020-10-04 10:49:26:698
arr4[]希尔排序后（移动法）的时间是：2020-10-04 10:49:26:710
