插入排序的算法复杂性分析(java实现)

一、问题描述与分析

问题:给定一个整数序列,有序或无序,然后用插入排序按照从小到大的顺序(确切地说,是非递减的顺序)排列序列中的整数。

分析:插入排序是在一个已经有序的小序列的基础上,一次插入一个元素(从第二个元素开始进行排序)。所以,刚开始这个有序的小序列只有1个元素,就是第一个元素。

比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。

二、 程序实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        //输入数组(序列)
        while (scanner.hasNext()) {
            //输入数组(序列)长度
            int length = scanner.nextInt();//自定义输入长度 即要排序的元素个数
            int[] arr = new int[length];
            //for循环输入数组元素
            for (int i = 0; i < length; i++) {
                arr[i] = scanner.nextInt();
            }
            insert(arr); //调用insert函数对数组做插入排序
            //做循环打印排序后的数组元素
            for (int element : arr) {
                System.out.print(element + " ");
            }
            break;
        }
    }

    //排序
    static void insert(int[] arr) {
        int i, j, tem;
        //i=1,即从第二个元素开始排序
        for (i = 1; i < arr.length; i++) {
            j = i - 1;//j初始为第i个元素前面的元素,即首先与之比较的元素
            tem = arr[i];//tem为数组的第i个元素,赋值到新的变量方便比较
            //循环比较,j--,一直比较到符合条件退出循环
            while (j >= 0) {
                //如果第i个元素小于第j个元素,后移
                if (tem < arr[j]) {
                    arr[j + 1] = arr[j];
                } else
                    break;//成功,退出循环
                j--;
            }
            j += 1;
            arr[j] = tem;//赋值
        }
    }
}

三、 实验结果与分析

实验结果:

插入排序

实验分析:

插入排序的时间复杂度分析。在最坏情况下,数组完全逆序,插入第2个元素时要考察前1个元素,插入第3个元素时,要考虑前2个元素,……,插入第N个元素,要考虑前 N - 1 个元素。因此,最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1),等差数列求和,结果为$$N^2/2$$,所以最坏情况下的复杂度为$$O(N^2)$$。最好情况下,数组已经是有序的,每插入一个元素,只需要考查前一个元素,因此最好情况下,插入排序的时间复杂度为$$O(N)$$。
平均复杂度为$$O(N^2)$$,空间复杂度为$$O(1)$$。

Last modification:July 6th, 2020 at 06:28 pm
如果觉得对你有用,请随意赞赏