排序算法之插入排序

插入排序

插入排序有三种排序方法：直接插入排序、折半插入排序和希尔排序

直接插入排序

原理

直接插入排序的原理比较简单，就是在一个有序的数列中，将待排序的数字插入到合适的位置，可能大家会有疑问了，哪里来的有序的序列啊？对于一个序列，我们认为一个数时肯定是有序的，所以序列中第一个数是有序的，我们从第二个数开始，把它插入到这个只有一个数的有序序列中，那么现在就有两个数的有序序列了，再把第三个数插入到这个有序序列中……

实现

public static void directInsertSort(int[] num) {
    for (int i = 1; i < num.length; i++) {
        for (int j = i; j > 0; j--) {
            if (num[j] < num[j - 1]) {
                num[j] = num[j] + num[j - 1];
                num[j - 1] = num[j] - num[j - 1];
                num[j] = num[j] - num[j - 1];
            }
        }
    }
}

折半插入排序

原理

折半插入排序其实是一种优化的直接插入排序，直接插入排序我们在插入时，是用待插入数和序列中的数一一对比，直到找到合适的位置，那么折半插入排序就是先和有序序列中间那个数比较，以
确认应该插入到前半还是后半部分，然后再折半……

实现

public static void binaryInsertSort(int[] num) {
    int insert;
    int pre;
    int last;
    int mid;
    for (int i = 1; i < num.length; i++) {
        insert = num[i];
        pre = 0;
        last = i - 1;
        while (pre <= last) {
            mid = (last + pre) / 2;
            if (insert > num[mid])
                pre = mid + 1;
            else
                last = mid - 1;
        }
        // 从插入位置开始往后移
        for (int j = i; j > pre; j--) {
            num[j] = num[j - 1];
        }
        num[pre] = insert;
    }
}

希尔排序

原理

希尔排序简单说就是进行分组的插入排序，首先确认一个步长，相距该步长上的数进行插入排序，然后再缩小该步长，再重复上述步骤，我们用一个图来表示更直观：

将用线连上的数进行排序即可

实现

public static void shellSort(int[] num) {
    int d = num.length / 2;
    int insert;
    int f;
    while (d != 0) {
        for (int i = d; i < num.length; i += d) {
            insert = num[i];
            f = i - d;
            while (f >= 0 && num[f] > insert) {
                num[f + d] = num[f];
                f = f - d;
            }
            num[f + d] = insert;
        }
        d /= 2;
    }
}