图解Java经典算法插入排序的原理与实现

目录

• 一、算法介绍
• 二、算法思想
• 三、算法原理
• 四、动图演示
• 五、代码实现
• 六、算法分析
• 6.1 时间复杂度
• 6.2 空间复杂度

一、算法介绍

插入排序，也称为直接插入排序。插入排序是简单排序中效率最好的一种，它也是学习其他高级排序的基础，比如希尔排序/快速排序，所以非常重要，而它相对于选择排序的优点就在于比较次数几乎是少了一半。

二、算法思想

每次将待排序的元素插入到已排序的序列中，直至全部插入完成。

三、算法原理

• 把所有元素分为两个序列，将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从未排序序列中的第一个元素开始，向已排序的序列中插入
• 倒序遍历已排序序列，依次和待插入的元素比较，找到一个小于或等于待插入的元素，插入到该元素后面，其余元素向后移动一位

四、动图演示

五、代码实现

核心代码

public class InsertionSort {
    //  插入排序
    public static void sort(Comparable[] a){
       for (int i = 1;i < a.length;i++){
           for (int j = i;j > 0;j--){
               //比较索引j处的值与索引j-1处的值,如果j-1索引处的值大，则交换数据，反之，则找到了合适的位置，退出循环
               if (greater(a[j - 1],a[j])){
                   swap(a,j - 1,j);
               }else{
                   break;
               }
           }
       }
    }
    //比较 v 是否大于 w
    public static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }
    //数组元素交换位置
    private static void swap(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

方法调用

public class InsertionSortTest {
    public static void main(String[] args) {
        Integer[] arr = {3,44,38,5,47,15,36,26,27};
        InsertionSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//排序前：{3,44,38,5,47,15,36,26,27}
//排序后：{3,5,15,26,27,36,38,44,47}

六、算法分析

6.1 时间复杂度

当待排序的 n 个元素是正序排列时，是排序的最佳情况，只需要比较（n-1）次，时间复杂度是O(n)；最坏的情况是该序列是反序排列，此时就需要比较n(n-1)/2次，时间复杂度为 O(n²)。

插入排序的平均时间复杂度为 O(n²)

6.2 空间复杂度

插入排序的空间复杂度为常数阶O(1)

到此这篇关于图解Java经典算法插入排序的原理与实现的文章就介绍到这了,更多相关Java插入排序内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！