算法面经--希尔排序

希尔排序

一、算法思路

简单插入排序存在的问题： 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。

希尔排序（缩小增量排序）：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

希尔排序1.png

二、代码实现

2.1 交换法 （数据量大时，速度慢）

 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++) { // 中位数右侧的所有数遍历
  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));
  }
  }

2.2 移位法（速度快，优化后的方法）---缩小增量+简单插入的结合并改良版

 // 对交换排序进行优化--移位法
  public static void shellSort2(int[] arr) {
  // 增量gap,并逐步缩小增量
  for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  // 从第gap个元素，逐个对其所在 的组进行直接插入排序
  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];// arr[insertIndex] {101, 101,
  // 119, 1}
  j -= gap;
  }
  // 当退出while后，就给temp找到插入的位置
  arr[j] = temp;
  }
  }
  }