算法(三)直接插入排序

直接插入排序的基本思想是:将需要排序的关键数与前面已经排好序的数据从后往前进行比较，使其插入到合适的位置。

基本步骤

排序数组为a[0...n]

1. 将a[0]作为起始数据，从a[1]开始作为关键字向前进行比较，若小于前面所遇到的比较数，则交换两个比较数的位置，否则直接进行下一个关键字的比较。
2. 重复前面的步骤，直到将a[n]作为关键字进行比较。比较完以后则排序结束。

该算法实现还是很简单的，可以根据步骤迅速写出

实现

public static void insertSort(int[] arr) {
        int temp;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {//交换
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {//只要比较不小于的话就直接跳出
                    break;
                }
            }
        }
    }

总结

通过上面的思想可以看出该排序为稳定排序，且最好时间复杂度、最坏时间复杂度都与前面的冒泡排序一样是O(n)与O(n^2)。

转载请指明出处 idisfkj博客：https://idisfkj.github.io