本文共 1216 字，大约阅读时间需要 4 分钟。

Java学习——排序算法之希尔排序（Shell排序）

• 什么是希尔排序？

希尔排序，又称缩小增量排序。其原理是：先确定一个增量ht（或称步长、间隔），然后将原序列按照增量分组，每个组按照直接插入法排序。接着，将增量ht/2，再按照这个增量分组，再进行直接插入排序，以此类推，直到增量ht为1时，整个序列就已经排序好了。

• 希尔排序的原理：

• 希尔排序的主要特点：

希尔排序每一趟是以不同的增量进行插入排序，我们很容易就能想到，当增量越大时，被移动的记录跳跃越大。到最后一躺排序时，很多元素已经有序，不需要移动多少，所以排序的速度提高了。其实，希尔排序也就是分组插入排序。

• 希尔排序的关键：

希尔排序的关键是：增量ht的选择，选择一个合适的增量可以大大的提升效率。

• 代码实现：

import java.util.Arrays;public class Test4 {    /**     * 希尔排序     */    public static void main(String[] args) {        //定义一个int类型的数组        int[] arr = {8,6,9,1,3,6,0,10};        //获取最大增量，这里我们使用Knuth提出的增量表达式：h=3*b+1        int ht = 1;        while (ht<=arr.length/3){            ht = 3 * ht+1;        }        System.out.println("选择的增量为："+ht);        //排序，最外层循环控制增量,每一次增量变为上一次的(h-1)/3，如果增量为1即排序完成（即h>0时排序完成）        for (int h = ht; h > 0 ; h=(h-1)/3) {            //里面两层循环对分组进行直接插入排序            for (int i = h; i < arr.length; i++) {                for (int j = i; j > h-1; j=j-h) {                    if (arr[j]

转载地址：http://axiwi.baihongyu.com/