十大经典排序算法之希尔排序

希尔排序

1959年Shell发明,第一个突破O(n²)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  1. 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

1 算法步骤

  1. 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
  2. 按增量序列个数 k,对序列进行 k 趟排序;
  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

2 动图演示

希尔排序)

java code

import org.junit.Test;
import java.util.Arrays;

public class ShellSort {
    @Test
    public void shell_sort() {
        int[] arr = {10, 7, 3, 6, 9, 200, 3, 4, 2, 1, 101, 2, 199};

        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3)
            gap = gap * 3 + 1; //<O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...

        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
package interview.sort;
import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {23, 44, 55, 6, 99, 4};
        shellSort(arr);
    }

    public static void shellSort(int[] arr) {
        int gap, i, j, temp;
        int length = arr.length;
        for (gap = length / 2; gap > 0; gap /= 2) {
            for (i = gap; i < length; i++) {
                for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
                    temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
        System.out.println("排序结果:" + Arrays.toString(arr));
    }
}