希尔排序，是插入排序的改进版。将数组内的值隔一段距离取出来当成一个新的数组排序，按照一定的间隔将整个数组排序完成后，缩小间隔在排序，一直到间隔为一的时候再排一次。那么这个时候排序完成。
如上图所示是间隔为4的时候进行排序，然后缩短间隔重复上边的步骤即可，一直缩短间隔到1的时候停止循环，这个时候就完成了排序。
直接看代码吧
package bubbling; /** * <p>希尔排序</p> * * @author zy 刘会发 * @version 1.0 * @since 2020/4/11 */ public class ShellSort { static void sort(int[] arr) { for (int w = 4; w > 0; w /= 2) { for (int i = w; i < arr.length; i++) { for (int j = i; j > w - 1; j -= w) { if (arr[j] < arr[j - w]) exchange(arr, j, j - w); } } } print(arr); } /** * 交换 * * @param a 要交换位置的数组 * @param i 要交换的位置(正确的位置) * @param j 最小值所在的位置 */ static void exchange(int[] a, int i, int j) { int temp = a[i];//用temp 最为第三方变量存储正确位置的值 a[i] = a[j];//将正确的值放到正确的位置 a[j] = temp; } static void print(int a[]) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + ","); } } public static void main(String[] args) { int[] arr = new int[]{9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2}; sort(arr); } }
这样的话是最初以间隔为4开始循环，每次除以2，也就是说第二次间隔为2，以此类推，这样就完成了排序。但是实际情况下间隔也不一定为4，有可能数组很大，那么以4为间隔就不太合适了。
最初的方式是将数组对半分开，无限分下去，直到不能再分。
package bubbling; /** * <p>希尔排序</p> * * @author zy 刘会发 * @version 1.0 * @since 2020/4/11 */ public class ShellSort { static void sort(int[] arr) { for (int w = arr.length / 2; w > 0; w /= 2) { for (int i = w; i < arr.length; i++) { for (int j = i; j > w - 1; j -= w) { if (arr[j] < arr[j - w]) exchange(arr, j, j - w); } } } print(arr); } /** * 交换 * * @param a 要交换位置的数组 * @param i 要交换的位置(正确的位置) * @param j 最小值所在的位置 */ static void exchange(int[] a, int i, int j) { int temp = a[i];//用temp 最为第三方变量存储正确位置的值 a[i] = a[j];//将正确的值放到正确的位置 a[j] = temp; } static void print(int a[]) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + ","); } } public static void main(String[] args) { int[] arr = new int[]{9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2}; sort(arr); } }
这种方式比较简单，据说希尔最初也是用这种方式的，但是有人提出了一个更好的序列来作为间隔!那就是Knuth序列
他张这个样子
h=1;
h=h*3+1;
有没有很眼熟？高中的时候没有有见过？
package bubbling; /** * <p>希尔排序</p> * * @author zy 刘会发 * @version 1.0 * @since 2020/4/11 */ public class ShellSort { static void sort(int[] arr) { int h = 1; while (h <= arr.length / 3) { h = h * 3 + 1; } for (int w = h; w > 0; w = (w - 1) / 3) { for (int i = w; i < arr.length; i++) { for (int j = i; j > w - 1; j -= w) { if (arr[j] < arr[j - w]) exchange(arr, j, j - w); } } } print(arr); } /** * 交换 * * @param a 要交换位置的数组 * @param i 要交换的位置(正确的位置) * @param j 最小值所在的位置 */ static void exchange(int[] a, int i, int j) { int temp = a[i];//用temp 最为第三方变量存储正确位置的值 a[i] = a[j];//将正确的值放到正确的位置 a[j] = temp; } static void print(int a[]) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + ","); } } public static void main(String[] args) { int[] arr = new int[]{9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2}; sort(arr); } }
到此结束，文笔不好，还请见谅!!!欢迎吐槽!!!