1.2.3希尔排序
希尔排序又叫缩小增量排序
基本思想：先取一个小于n的整数作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
具体算法步骤：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
实例：
空间效率：仅使用常数个辅助单元，因而空间复杂度为O(1)
时间效率：最坏情况下希尔排序的时间复杂度为O（n^2）
稳定性：相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，所以是不稳定的排序方法
适用性：仅适用于当线性表为顺序存储的情况
import java.util.Scanner; import java.util.Arrays; public class ShellSort { public static void shellInsert(int[] arr) { for (int dis = arr.length/2;dis>0;dis = dis/2){ for (int i=dis;i<arr.length;i++){ // 开始组内比较 int temp = arr[i]; int j = i-dis; while (j>=0 && temp < arr[j]){ // 前面的比后面的大，则交换位置 arr[j+dis] = arr[j]; // 大的放到后面来 j = j - dis; } arr[j+dis] = temp; } } System.out.println("希尔排序："+Arrays.toString(arr)); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据 while (scanner.hasNext()) { int n = scanner.nextInt(); if (n > 0) { int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } shellInsert(arr);//调用希尔排序shellInsert方法 } } } }
