排序算法（三）：直接插入排序

直接插入排序算法的思路

1、将n个待排序的元素看成是由一个有序表和一个无序表组成，其中最开始有序表中只包含第一个元素，无序表包含n-1个元素。
2、排序的过程中，每次从无序表中取出第一个元素，将其与有序表中的元素进行比较，插入到有序表中适当的位置，对有序表进行更新。
3、最终的有序表即是最终的排序结果。

直接插入排序算法的性质

1、最坏时间复杂度：O（n^2）
2、平均时间复杂度：O（n^2）
3、稳定性：稳定

直接插入排序算法的代码实现

这里进行从小到大排序

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //待插入的数
            int insertVal = arr[i];
            //待插入数前面数的下标
            int insertIndex = i - 1;
            //  给 insertVal 找到插入的位置
            // 说明
            // 1. insertIndex >= 0  保证在给 insertVal 找插入位置的过程中，不越界
            // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            // 3.  就需要将 arr[insertIndex] 后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            //如果要从大到小排序，则条件改为insertVal > arr[insertIndex])
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // 当退出 while 循环时，说明插入的位置找到, insertIndex + 1
            // 加一个判断条件:判断现在是否已经找到了待插入的位置
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

主方法进行验证

public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89,23,33};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

结果：[-1, 1, 23, 33, 34, 89, 101, 119]

最后

以上就是踏实苗条为你收集整理的排序算法（三）：直接插入排序的全部内容，希望文章能够帮你解决排序算法（三）：直接插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。