插入排序

发表于 | 分类于

介绍

  1. 6 5 3 1 8 7 2 4—>首先是位置1上的数和位置0上的数进行比较，
    如果位置1上的数更小，就和位置0上的数进行交换，
  2. 考察位置2上的数，如果位置2上的数比位置1的数小，就进行交换，继续如果比位置0小，继续进行交换，
  3. 一次从1位置到n-1位置进行比较，直到全部插入。

指标

  • 时间复杂度
    和数据状态有关
    最好（已经顺序）O(n)
    最坏（逆序的） O(n²)
    按最差情况估计复杂度 O(n²)
  • 空间复杂度O(1)

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class InsertionSort {

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		//后面的牌，逐渐插入前面的有序区间
		//开始时候，有序区间为 i = 0
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	private static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	private static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
		int[] arr = new int[] {3,5,4,2,6,7,1,9,8};
		insertionSort(arr);
		printArray(arr);
	}
}

输出

排序后

> >