插入排序
收录于
学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
插入排序是一个简单的排序算法，算法主要通过在左边维持一个有序的子数组，然后不断的将右边的元素按照顺序插入到左边有序的子数组中，直到所有的元素都插入完成。最好的情况是当数组已经有序时，时间复杂度是O(N)，最坏的情况是当数组是反序时，时间复杂度是O(N^2)，平均时间复杂度是O(N^2)。
算法主要思路是
- 从数组第二个元素开始，按照顺序插入到当前元素左边已经有序的子数组中。
- 第一轮，左边的子数组只有一个元素，只要和当前元素比较，交换位置即可。
- 第二轮，左边的子数组有两个上一轮已排好序的两个元素，需要将当前元素插入到两个元素中合适的位置。
- ....
- 直到所有的元素都插入，数组就排序完成。
比如数组[4, 2, 1, 3, 7, 6, 5]插入排序过程如下
1/6
插入排序代码实现如下。
1import java.util.Arrays;
2
3public class Main {
4
5 public static void main(String[] args) {
6 int[] arr = {4, 2, 1, 3, 7, 6, 5};
7 insertionSort(arr);
8 System.out.println(Arrays.toString(arr));
9 }
10
11 /**
12 * 插入排序
13 * 在左边维持一个有序的子数组
14 * 然后不断的将右边的元素按照顺序插入到左右有序的子数组中
15 * 直到所有的元素都插入完成
16 *
17 * @param arr
18 */
19 public static void insertionSort(int[] arr) {
20 for (int j = 1; j < arr.length; j++) {
21 int current = arr[j];
22 int i = j - 1;
23
24 /**
25 * 在有序数组中寻找合适的位置
26 */
27 while (i >= 0 && current < arr[i]) {
28 arr[i + 1] = arr[i];
29 --i;
30 }
31 /**
32 * 插入到左边有序数组中合适的位置
33 */
34 arr[i + 1] = current;
35 }
36 }
37}
38注意: 这个Java运行环境不支持自定义包名，并且public class name必须是Main
插入排序也是一种效率比较低的排序算法，一般适用于对效率要求不高或者数据规模较小的排序。
排序算法插入排序
1