排序算法比较与梳理

各类排序算法

排序算法一般分类：

相关概念：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

冒泡排序

原理

比较两个相邻的元素，将值大的元素交换至右端。

思路

依次比较两个相邻的数，将小数放到前面，大数放到后面

第一趟：首先比较第 1 个数和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数，将小数放前，大数放后，如此一直继续下去，直到比较最后两个数，将小数放前，大数放后。然后重复第一趟步骤，直到所有排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较。

第二趟完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较。

依此类推……

代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {2,4,1,5,67,2,45,78,3,9};
        bubbleSort(array);
    }

    public static void bubbleSort(int[] array){
        for(int i = 0 ; i < array.length-1; i++){
            for(int j = 0 ; j < array.length-1; j++){
                if(array[j] > array[j+1]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println("排序后的数组为:" + Arrays.toString(array));
    }
}

输出结果：

排序后的数组为: [1, 2, 2, 3, 4, 5, 9, 45, 67, 78]

特点分析

冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

用时间复杂度来说： 如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。如果很不幸我们的数据是反序的，则需要进行 n - 1 趟排序。每趟排序要进行 n - i 次比较(1 ≤ i ≤ n - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。

• 冒泡排序的最坏时间复杂度为：O(n^2)
• 冒泡排序的最好时间复杂夫为：O(n)
• 冒泡排序的平均时间复杂度：O(n)
• 冒泡排序是一种稳定的排序算法

快速排序

原理

从一个数组中随机选出一个数N，通过一趟排序将数组分割成三个部分，1、小于N的区域 2、等于N的区域 3、大于N的区域，然后再按照此方法对小于区的和大于区分别递归进行，从而达到整个数据变成有序数组。

思路

如下图：

假设最开始的基准数据为数组的第一个元素23，则首先用一个临时变量去存储基准数据，即 tmp=23，然后分别从数组的两端扫描数组，设两个指示标志：low 指向起始位置，high 指向末尾。

首先从后半部分开始，如果扫描到的值大于基准数据就让 high - 1，如果发现有元素比该基准数据的值小，比如上面的 18 <= tmp ，就让high位置的值赋值给low位置，结果如下：

然后开始从前往后扫描，如果扫描到的值小于基准数据就让 low+1，如果发现有元素大于基准数据的值，比如上图 46 >= tmp，就再将 low 位置的值赋值给 high 位置的值，指针移动并且数据交换后的结果如下：

然后再开始从前往后遍历，直到 low=high 结束循环，此时 low 或者 high 的下标就是基准数据23在该数组中的正确索引位置，如下图所示：

这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。

然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {2,4,1,5,67,2,45,78,3,9};
        quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array,int low,int high){
        if(low < high){
            //找到基准数据位置
            int index = getIndex(array,low,high);
            //递归
            quickSort(array,0,index-1);
            quickSort(array,index+1,high);
        }
    }

    //获取基准数据位置
    public static int getIndex(int[] array,int low,int high){
        //一般取第一个数作为基准数据
        int tmp = array[low];
        while(low < high){
            while(low < high && array[high] >= tmp){
                high--;
            }
            //否则high处元素小于基准数据，将high处赋值给low处数据
            array[low] = array[high];
            //赋值完后，需要从前面开始扫描数组
            while(low < high && array[low] <= tmp){
                low++;
            }
             array[high] = array[low];

        }
        //整个循环结束时high=low,但是该位置处不等于基准元素
        array[low] = tmp;
        return low;
    }
}

输出结果：

[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]

特点分析

最好情况下快排每次能恰好均分序列，那么时间复杂度就是 O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为 O(n^2)。

• 平均时间复杂度是 O(nlogn)
• 最坏时间复杂度是 O(n^2)
• 对于大的，乱序排列的数组来说快排一般是已知的最快的已知排序
• 快排是一种不稳定排序

插入排序

原理

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n^2)。是稳定的排序方法。

思路

将一个数据插入到已经排好序的有序数据中

• 将要排序的是一个乱的数组 int[] arrays = {3, 2, 1, 3, 3}
• 在未知道数组元素的情况下，我们只能把数组的第一个元素作为已经排好序的有序数据，也就是说，把{3}看成是已经排好序的有序数据

第一趟排序：

用数组的第二个数与第一个数(看成是已有序的数据)比较

• 如果比第一个数大，那就不管他
• 如果比第一个数小，将第一个数往后退一步，将第二个数插入第一个数去

第二趟排序：

用数组的第三个数与已是有序的数据 {2,3} (刚才在第一趟排的)比较

• 如果比 2 大，那就不管它
• 如果比 2 小，那就将 2 退一个位置，让第三个数和1比较

在第二步中：

• 如果第三个数比 1 大，那么将第三个数插入到 2 的位置上
• 如果第三个数比 1 小，那么将 1 后退一步，将第三个数插入到 1 的位置上

…

后面依此类推

代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] array = {2,4,1,5,67,2,45,78,3,9};
        insertSort(array);
    }


    public static void insertSort(int[] arr) {
        if (arr.length < 2)
            System.out.println(Arrays.toString(arr));

        for (int i = 1;i < arr.length;i++) {
            for (int j = i;j > 0;j--) {
                if (arr[j-1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                } else {
                    break;//插入新的元素
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

输出结果：

[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]

特点分析

• 最坏时间复杂度为O(n^2)
• 最好时间复杂度为O(n)
• 平均时间复杂度为O(n^2)
• 插入排序是一种稳定的排序算法。

选择排序

原理

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

思路

举例：数组 int[] arr = {5,2,8,4,9,1}

第一趟排序： 原始数据：5 2 8 4 9 1

最小数据1，把1放在首位，也就是1和5互换位置，

排序结果：1 2 8 4 9 5

第二趟排序：

第1以外的数据{2 8 4 9 5}进行比较，2最小，

排序结果：1 2 8 4 9 5

第三趟排序：

除1、2以外的数据{8 4 9 5}进行比较，4最小，8和4交换

排序结果：1 2 4 8 9 5

第四趟排序 :

除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换

排序结果：1 2 4 5 9 8

第五趟排序：

除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换

排序结果：1 2 4 5 8 9

代码实现

public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {2,4,1,5,67,2,45,78,3,9};
        selectionSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    public static void selectionSort(int[] array,int start,int end){
        for(int i = 0; i < array.length ;i++){
            int k = i;
            for(int j = k + 1; j < array.length; j++){
                if(array[j] < array[k]){
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = array[i];
                array[i] = array[k];
                array[k] = temp;
            }
        }
    }
}

输出结果：

[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]

特点分析

表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n^2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

• 最坏时间复杂度为O(n^2)
• 平均时间复杂度为O(n^2)
• 选择排序是一种不稳定的排序

堆排序

原理

堆排序是对简单选择排序的改进，简单选择排序是从 n 个记录中找出一个最小的记录，需要比较 n - 1 次。但是这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

思路

将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的 n - 1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次最大值。如此反复执行，就能得到一个有序序列了。

实现思路：

• 将初始待排序关键字序列 (R1,R2….Rn) 构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1] <= R[n]；
• 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 (R1,R2….Rn-2) 和新的有序区 (Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n - 1，则整个排序过程完成。

代码实现

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20};
        System.out.println("排序之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        // 堆排序
        heapSort(arr);

        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 堆排序
     */
    private static void heapSort(int[] arr) {
        // 将待排序的序列构建成一个大顶堆
        for (int i = arr.length / 2; i >= 0; i--) {
            heapAdjust(arr, i, arr.length);
        }

        // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
        }
    }

    /**
     * 构建堆的过程
     *
     * @param arr 需要排序的数组
     * @param i   需要构建堆的根节点的序号
     * @param n   数组的长度
     */
    private static void heapAdjust(int[] arr, int i, int n) {
        int child;
        int father;
        for (father = arr[i]; leftChild(i) < n; i = child) {
            child = leftChild(i);

            // 如果左子树小于右子树，则需要比较右子树和父节点
            if (child != n - 1 && arr[child] < arr[child + 1]) {
                child++; // 序号增1，指向右子树
            }

            // 如果父节点小于孩子结点，则需要交换
            if (father < arr[child]) {
                arr[i] = arr[child];
            } else {
                break; // 大顶堆结构未被破坏，不需要调整
            }
        }
        arr[i] = father;
    }

    // 获取到左孩子结点
    private static int leftChild(int i) {
        return 2 * i + 1;
    }

    // 交换元素位置
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }
}

输出结果：

排序之前：
50 10 90 30 70 40 80 60 20 
排序之后：
10 20 30 40 50 60 70 80 90

特点分析

堆排序时间复杂度：O(nlogn)

堆排序对原始记录的排序状态并不敏感，其在性能上要远远好过于冒泡、简单选择、直接插入排序。

归并排序

原理

归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

思路

比如我们对[8,4,5,7,1,3,6,2]这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

代码实现

public class MergeSort {
    public static void main(String []args){
        int[] array = {2,4,1,5,67,2,45,78,3,9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左序列指针
        int j = mid+1;//右序列指针
        int t = 0;//临时数组指针
        while (i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j<=right){//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){
            arr[left++] = temp[t++];
        }
    }
}

输出结果：

[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]

特点分析

• 归并排序是一种稳定排序
• Java中的Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本
• 每次合并操作的时间复杂度为O(n)，完全二叉树的深度为|log2n|，总的平均时间复杂度为O(nlogn)
• 归并排序的最好、最坏、平均时间复杂度都为O(nlongn)

计数排序

原理

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为 O(n+k)，其中 k 是整数的范围。基于比较的排序算法时间复杂度最小是 O(nlogn) 的。注意：计数排序对于实数的排序是不可行的（下面会解释）。该算法于1954年由 Harold H. Seward 提出。 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

思路

实现思路：

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
• 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。

代码实现

package ttt;
 
public class CountingSort {
    public static int[] countingSort(int[] theArray) {
    	int[] lastArray = new int[theArray.length];
        for(int i = 0; i < theArray.length; i++) {
        	int count = 0;
        	for(int j = 0; j < theArray.length; j++) {
        		if(theArray[i] > theArray[j]) {
        			count++;
        		}
        	}
        	lastArray[count] = theArray[i];
        }
    	return lastArray;
    }
    public static void main(String[] args) {
    	int []theArray = {6, 4, 5, 1, 8, 7, 2, 3};
        System.out.print("之前的排序：");
        for(int i = 0; i < theArray.length; i++) {
            System.out.print(theArray[i] + " ");
        }
        
        int []resultArray = countingSort(theArray);
        
        System.out.print("计数排序：");
        for(int i = 0; i < resultArray.length; i++) {
            System.out.print(resultArray[i] + " ");
        }
    }
}

输出结果：

之前的排序：6 4 5 1 8 7 2 3 计数排序：1 2 3 4 5 6 7 8

特点分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是 O(n+k)，空间复杂度也是 O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序

原理

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

思路

实现思路：

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

代码实现

public static void bucketSort(int[] arr){
    
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    //桶数
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    //将每个元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    
    System.out.println(bucketArr.toString());
    
}

特点分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序

原理

数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

思路

实现思路：

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

代码实现

public class RadixSort {
    private static void radixSort(int[] array,int d){
        int n=1;//代表位数对应的数：1,10,100...
        int k=0;//保存每一位排序后的结果用于下一位的排序输入
        int length=array.length;
        int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order=new int[length];//用于保存每个桶里有多少个数字
        while(n<d)
        {
            for(int num:array) //将数组array里的每个数字放在相应的桶里
            {
                int digit=(num/n)%10;
                bucket[digit][order[digit]]=num;
                order[digit]++;
            }
            for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
            {
                if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                {
                    for(int j=0;j<order[i];j++)
                    {
                        array[k]=bucket[i][j];
                        k++;
                    }
                }
                order[i]=0;//将桶里计数器置0，用于下一次位排序
            }
            n*=10;
            k=0;//将k置0，用于下一轮保存位排序结果
        }

    }
    public static void main(String[] args){
        int[] A=new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
        radixSort(A, 100);
        for(int num:A)
        {
            System.out.println(num);
        }
    }
}

特点分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 O(n) 的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n) 的时间复杂度。假如待排数据可以分为 d个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。

基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。

希尔排序

原理

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

思路

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

代码实现

public static void ShellSort(int num[]) {
    int temp;
    //默认步长为数组长度除以2
    int step = num.length;
    while (true) {
        step = step / 2;
        //确定分组数
        for (int i = 0; i < step; i++) {
            //对分组数据进行直接插入排序
            for ( int j = i + step; j < num.length; j = j + step) {
                temp=num[j];
                int k;
                for( k=j-step;k>=0;k=k-step){
                    if(num[k]>temp){
                        num[k+step]=num[k];
                    }else{
                        break;
                    }
                }
                num[k+step]=temp;
            }
        }
        if (step == 1) {
            break;
        }
    }
}

特点分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

参考资料

1. 图解排序算法(四)之归并排序
2. Java中的经典算法之冒泡排序(Bubble Sort)
3. Java中的经典算法之选择排序（SelectionSort）
4. 快速排序
5. 图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)
6. 十大经典排序算法（动图演示）