经典排序算法(三) —— Shell Sort 希尔排序

目录

简介

1959年由Shell发明,是第一个突破O(n2)的排序算法,是简单插入排序的改进版。

它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。

希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2)。

排序过程

经典排序算法(三)  —— 	Shell Sort	希尔排序

实现


/**
     * 希尔排序
     *
     * @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)
上一篇:排序--希尔排序


下一篇:数据结构--排序