插入排序【Java实现】

插入排序【Java实现】,第1张

文章目录
  • 插入排序
    • 基本介绍
    • 举例
    • 代码实现
    • 测试
    • 插入排序的复杂度

插入排序 基本介绍

插入排序是将数组中的元素分为两个区间,已排序区间与未排序区间,将数组中的第一个元素作为初始的已排序区间,其他元素作为为排序区间,然后遍历,逐个取未排序区间的元素与已排序区间的元素作比较,并将其插入到合适的位置,保证已排序区间的元素一直有序,直到未排序区间的元素为空,排序结束。

举例

代码实现
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int insert = arr[i];	//要插入的元素
        int j = i - 1;	//前一个元素
        for (; j >= 0; j--) {
            if (arr[j] > insert) {//若前一个元素大于插入的元素,就交换位置
                arr[j + 1] = arr[j];
            } else {//如果前一个元素小于插入的元素,直接退出
                break;
            }
        }
        arr[j + 1] = insert;
    }
}
测试
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {2, 5, 4, 1, 3, 6};//初始数组
        System.out.println("排序前");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }

        System.out.println();

        insertionSort(arr);//调用排序方法
        System.out.println("排序后");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insert = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > insert) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = insert;
        }
    }
}

测试结果

排序前
2	5	4	1	3	6	
排序后
1	2	3	4	5	6	
插入排序的复杂度

从实现过程可以看出,插入排序不需要额外的存储空间,所以空间复杂度是O(1),即插入排序是一个原地排序算法

最好的情况,初始数组是有序的,不需要移动任何数据,此时,时间复杂度是O(N)

最坏的情况,初始数组是倒序的,每次插入都要移动已排序区间,此时,时间复杂度是O(N2)

综上,插入排序的时间复杂度是O(N2)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/789978.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存