java算法排序之希尔排序

package 十大排序; public class 希尔排序 { /* 时间复杂度：O(n log n) 空间复杂度: O(1) 稳定性： 不稳定 */ public static void main(String[] args) { int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1}; sort(arr); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } private static void sort(int[] arr) { //不断的缩小增量 for (int interval = arr.length / 2; interval > 0; interval = interval / 2) { //使用插入算法 // int curEle, preIndex; // 记录当前待排序元素和前一个元素的下标. for (int i = interval; i < arr.length; i++) { int preIndex = i - interval; int curEle = arr[i]; while (preIndex >= 0 && arr[preIndex] > curEle) { //后移 arr[preIndex + interval] = arr[preIndex]; //preIndex往前查找大的也后移 preIndex = preIndex - interval; } //把比较小的位置放入 arr[preIndex + interval] = curEle; } } } }