Java：插入排序

排序的概念

插入排序

直接插入排序

哈希排序

排序的概念

排序：所谓的排序，就是使一串记录，按照某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种算法>排序算法是稳定的；否则称为不稳定的。

常见的算法>排序算法有下面四种：

插入排序：直接插入排序，希尔排序
选择排序：选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序：归并排序

这里主要介绍Java如何实现插入排序中的直接排序和希尔排序。

插入排序

基本思想：把待排序的记录按照其关键码值的大小逐个插入到一个已经拍好的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。生活中的例子，就像我们在完扑克牌的时候机型排序一样。

直接插入排序

思路：

直接插入排序的过程就像是有一组无序数据，用第二个元素先和第一个元素比较，如果第一个元素比第二个元素大，那么二者就交换位置，否则继续往后推，随着往后推，每一次前一个元素都要不断和之前排序过的元素进行比较。

Sort类

public class Sort {
    /**
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定的排序
     * @param array
     */
    //直接插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    arr[j+1] = tmp;
                    break;
                }
            }
            //确保j位置的数，也就是前一个数能换位成功
            arr[j+1] = tmp;
        }
    }
}

Test类测试类

public class Test {
    public static void main(String[] args) {
        int[] arr = {12,6,59,45,73,26,2};
        System.out.println("排序前：" + Arrays.toString(arr));
        Sort.insertSort(arr);
        System.out.println("排序前：" + Arrays.toString(arr));
    }
}

输出结果为：

关于i=1，且i < arr.length思路，因为数组是从0开始的，所以arr[6]的位置刚好是最后一位。

通过上面的动图我们不难发现，如果数组一开始越有序，直接插入排序的效率越高，这也为下面的哈希排序提供了思路。

稳定性

直接插入排序是稳定的，由上面图片能看到它是具有稳定性的，但如果是代码部分的 arr[j] > tmp 改为：arr[j] >= tmp，以上面的2a和2b为例，它们的顺序就会发生变化。那么这还能说直接插入排序是稳定的吗？

当然能，因为本身是一个稳定的排序，那么可以实现为不稳定的。

但是，如果一个排序本身是不稳定的，那就不能实现稳定的排序。

哈希排序

哈希排序可以看作是直接插入排序的优化，先通过 gap来不断简化其中的有序性，然后再用直接插入排序，越有序，直接插入排序的时间复杂度越小，速度越快。

通过间隔分为不同的组，组内进行排序，然后再缩短gap来进行再次排序。

代码为

public static void shellInsert(int[] array){
    int gap = array.length;
    while(gap > 1){
        gap /= 2;
        shell(array, gap);
    }
}

private static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0; j-= gap) {
            if(array[j] > tmp){
                array[j+gap] = array[j];
            }else{
                array[j+gap] = tmp;
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

到这里，插入排序中的直接插入排序和希尔排序就结束了，接下来我会继续给出剩下排序的思路和代码。