排序之插入排序

插入排序

1.概念：插入排序，也叫直接插入排序。其核心思想是在将一个数据插入到一个已经排序好的数据中，从而得到一个新的，有序的新表。在数据量少的时候，这是一个不算的有序算法。其实现过程使用双循环，外循环对第一个元素之外的所有元素，内循环对当前元素前面的有序表进行插入位置查找，并进行移动。
2.使用情形
插入排序的平均时间复杂度为o（n^{2），空间复杂度为常数阶o（1），其具体的时间复杂度和数组的有序性也是有关联的。当数组有序时，是最优的情况，只需要比较N-1次（N为元素个数），时间复杂度为o（N）。最坏的情况是排序是逆序的，此时的时间复杂度为o（n}2）。
3.过程演示
假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

从小到大的插入排序整个过程如图示：

第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。

第二轮：第三位置的9比前面的7大，不需要交换位置

第四轮：第四位置上的3比前面的9小，交换位置，依次往前比较。

第五轮：第五位置上的1比前面的9小，交换位置，再一次进行比较。

…

就这样依次比较到最后一个元素。
4.java代码实现

public class SortDemo {

    public static void main(String[] args) {

        int[] compareArr = new int[] {7, 9, 6, 3, 1, 5, 2, 4, 8};
        SortDemo.sort(compareArr);
        for (int i : compareArr) {
            System.out.println(i);
        }

    }

    private static void sort(int[] compareArr) {

        for (int i = 0; i < compareArr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (compareArr[j] < compareArr[j - 1]) {
                    SortDemo.swap(compareArr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    private static void swap(int[] compareArr, int i, int j) {

        int k = compareArr[i];
        compareArr[i] = compareArr[j];
        compareArr[j] = k;
    }
}