数据结构-插入排序实现
文章目录
- 1、描述
- 2、代码实现
- 3、结果
- 4、复杂度
1、描述
待排序的数组分为已排序、未排序两部分;
初始状态时，仅有第一个元素为已排序序列，第一个以外的元素为未排序序列；
此后遍历未排序序列， 将元素逐一插入到已排序的序列中：即把该为排序元素与原有一排序序列当做一个新序列，通过一次冒泡排序整合成已排序序列（从右侧开始，两个相邻元素进行比较，匹配成功则换位置，不成功就不做变动）
例：
| 源数据 | 3 | 2 | 1 |
|---|---|---|---|
| 步骤1 (3为已排序，2、1 为未排序；3 和 2 比较) | 2 | 3 | 1 |
| 步骤2.1 (2、3为已排序，1为未排序；3 和 1 比较) | 2 | 1 | 3 |
| 步骤2.2 (2 和 1 比较) | 1 | 2 | 3 |
2、代码实现
public class SimpleInsertSort {// 数组长度public final static int MAX_SIZE = 10;// 复杂度public static long complexity = 0;// 打印public static void print(Object[] params) {System.out.println(Arrays.toString(params));}public static void main(String[] args) {Integer[] arr = new Integer[MAX_SIZE];// 数组填充数据for (int i = 0; i < arr.length; i++) {arr[i] = Integer.valueOf(Math.round(Math.random() * 100) + "");}System.out.printf("数据：");print(arr);// 第 i 位置数据和前置数据作比较for (int i = 1; i < arr.length; i++) {int temp = arr[i];// 进入循环前0-(i-1)范围的数据已经是排序数据；跳出后表示0-i已排序// < temp: 降序 ; > temp: 升序// 该循环相当于冒泡排序（局部）for (int j = i; j > 0 && arr[j-1] > temp; j--) {complexity++;arr[j] = arr[j-1];arr[j-1] = temp;}}System.out.printf("结果：");print(arr);System.out.println("复杂度：" + complexity);}
}
3、结果
数据：[12, 18, 75, 25, 71, 59, 84, 42, 87, 13]
结果：[12, 13, 18, 25, 42, 59, 71, 75, 84, 87]
复杂度：16
4、复杂度
最好情况，第二个循环都不需要执行，O(N)
最坏情况，第一个以外的元素都需要和之前的数据做一次交换 O(N*N)