经典排序算法（三） —— Shell Sort 希尔排序

• 简介
• 排序过程
• 实现
• 复杂度

简介

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）