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