package Sort.Compareable; public class ShellSort { public static Comparable[] shellSort(Comparable[] arr) { //1.确定增长量 int h = 1; while (h < arr.length / 2) { h = 2 * h + 1; } //2.h逐步递减,当h递减为1的时候排序完成 while (h >= 1) { //2.1增量确定,对每一组进行排序 //找到待插入的数据 for (int i = h; i <= arr.length - 1; i++) { //2.2把待插入的元素插入到有序数组中 for (int j = i; j >= h; j -= h) { //判断arr[j]是否小于arr[j-h],若是的话,改变两个元素的位置 if(arr[j].compareTo(arr[j-h])<0){ swap(arr,j,j-h); } } } //2.3变化增量 h = h / 2; } return arr; } private static void swap(Comparable[] arr, int j, int i) { Comparable temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }