基本排序算法 - 希尔排序
简单插入排序存在一定的问题：
当待插入的数比较小时，会进行多次比较并进行多次的后移赋值操作，影响效率。
希尔排序也是一种插入排序，是希尔（Donald Shell）在1959年提出的一种排序算法。它是简单插入排序经过改进后的一个更高效的版本，也称为缩小增量排序。
希尔排序基本思想
希尔排序是把元素按照下标的增量进行分组，对每组元素直接使用插入排序。这样随着增量的逐步减少，数组会越来越有序，当增量减至1时，执行完该轮排序后，希尔排序结束。
图示与代码
根据对有序序列在插入时采用的方法不同，希尔排序又可分为交换法和移动法。
希尔排序 - 交换法
public class ShellSort {public static void main(String[] args) {int[] arr = {5, 21, 9, 6, 10, 2, 16};int len = arr.length;int temp = 0;int count = 0;System.out.println("原数组：" + Arrays.toString(arr));for (int gap = len / 2; gap > 0; gap /= 2) {// 分成的组数为gapfor (int i = gap; i < len; i++) {// 遍历各组中所有的元素，步长gapfor (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));}}}
打印结果：
原数组：[5, 21, 9, 6, 10, 2, 16]
第1轮：[5, 10, 2, 6, 21, 9, 16]
第2轮：[2, 5, 6, 9, 10, 16, 21]
希尔排序 - 移动法
该方法跟交换法大体一样，只是进行组内排序时采用了移动法（可看成一个插入排序）
public class ShellSort1 {public static void main(String[] args) {int[] arr = {5, 21, 9, 6, 10, 2, 16};int len = arr.length;int count = 0;System.out.println("原数组：" + Arrays.toString(arr));// 增量为gap，并逐步缩小增量for (int gap = len / 2; gap > 0; gap /= 2) {// 从第gap个元素，逐个对其所在组进行直接插入排序for (int i = gap; i < len; i++) {int j = i;int temp = arr[j];while (j - gap >= 0 && temp < arr[j - gap]) {// 移动 这里和插入排序是一样的原理arr[j] = arr[j - gap];j -= gap;}// while退出后就给temp找到了插入位置arr[j] = temp;}System.out.println("第"+(++count)+"轮："+Arrays.toString(arr));}}}
发布评论