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