希尔排序

阅读量: 459 编辑

希尔排序 - shellSort

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

一、排序步骤

  • 1、按增量序列个数 k,对序列进行 k 趟排序;

  • 2、每趟排序,根据对应的增量 ti,将待排序列分割成若干长度的子序列,分别对各子表进行直接插入排序。

  • 3、仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

二、Java代码

public static int[] shellSort(int[] array) {
    if (array.length == 0)
        return array;

    int length = array.length,
        gap = length / 2,
        tmp;

    while (gap > 0) {
        //针对gap间隔的数据进行插入排序
        for (int i = gap; i < length; i++) {
            tmp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > tmp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = tmp;
        }
        gap /= 2;
    }

    return array;
}

三、代码总结

是插入排序的一种改进版。

  • 1、双重循环:外循环遍历增量,内循环从未排序的子序列元素中找到最小值。

  • 2、将最小值和子序列中已排序序列之后的数据交换。

苏ICP备13052010号-3
©2022 南京匠成信息科技有限公司