Loading... *插入排序的算法复杂性分析（java实现）* **一、问题描述与分析** 问题：给定一个整数序列，有序或无序，然后用插入排序按照从小到大的顺序（确切地说，是非递减的顺序）排列序列中的整数。 分析：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素（从第二个元素开始进行排序）。所以，刚开始这个有序的小序列只有1个元素，就是第一个元素。 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。 **二、 程序实现** ```java 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;//赋值 } } } ``` **三、 实验结果与分析** 实验结果： ![插入排序][1] 实验分析： 插入排序的时间复杂度分析。在最坏情况下，数组完全逆序，插入第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)$$。 [1]: https://img.xiaowuyike.com/images/2020/07/06/iarupdxu.md.png Last modification：July 6th, 2020 at 06:28 pm © 允许规范转载 Support 如果觉得对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
