关于Java排序算法-希尔排序（Shell Sort）

希尔排序又称“缩小增量排序”，是通过对直接插入排序进行改进得到的一种插入排序法。
基本思想：将整个待排序列分割成几个较小的子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对整个记录序列进行一次直接插入排序。
过程：设待排序列有n个记录, 首先取一个整数d1< n 作为步长, 将全部记录分为d1个子序列, 所有距离为d1的记录放在同一个子序列中, 在每个子序列中分别施行直接插入排序。然后缩小步长 , 如取 d2=d1/2，重复上述的子序列划分和排序工作。直到最后取dt=1， 将所有记录放在同一个序列中排序为止。

public class SortTest {
  public static void main(String[] args) {
    int[] arr = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 4 };
    display("原始数据 : ", arr);
    // 希尔排序
    shellSort(arr);
    display("排序结果:", arr);
  }

  // 交换元素
  public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }
  
  // 显示
  public static void display(String str, int[] arr) {
    System.out.println(str);
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 希尔排序
  public static void shellSort(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;
        while (j - gap >= 0 && arr[j] < arr[j - gap]) {
          // 插入排序采用交换法
          swap(arr, j, j - gap);
          j -= gap;
        }
      }
    }
  }

}

原始数据 :
49 38 65 97 76 13 27 49 55 4
排序结果:
4 13 27 38 49 49 55 65 76 97