插入排序的算法复杂性分析（java实现）

插入排序的算法复杂性分析（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)$$。