1959年由Shell发明,是第一个突破O(n2)的排序算法,是简单插入排序的改进版。
它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。
希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2)。
/** * 希尔排序 * * @param arr n * @return */ public static int[] sort(int[] arr) { int n = arr.length; int gap = n; while ((gap /= 2) != 0) { for (int i = 0; i + gap < n; i++) { int tmp = i; while (tmp != -1 && arr[tmp] < arr[tmp + gap]) { exchangeArrayEle(arr, tmp, tmp + gap); tmp -= 1; } } } return arr; } /** * 交换数组元素 * 临时变量法 * * @param nums 数组 * @param i 待交换元素i * @param j 待交换元素j */ public static void exchangeArrayEle(int[] nums, int i, int j) { Assert.assertNotNull(nums); int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
O(n^3/2)