插入排序

(Updated: )
排序算法

过程

1、从数组第2个元素开始抽取元素。

2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。

3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。

动图展示

代码实现

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
/**
 * 插入排序
 */

public class InsertSort {

    public static int[] insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int k = i - 1;
            while (k >= 0 && arr[k] > temp) {
                k--;
            }
            //腾出位置插进去,要插的位置是 k + 1;
            for (int j = i; j > k + 1; j--) {
                arr[j] = arr[j - 1];
            }
            //插进去
            arr[k + 1] = temp;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 1, 4, 6};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}

性质：

  1. 时间复杂度：O(n2)
  2. 空间复杂度：O(1)
  3. 稳定排序
  4. 原地排序

参考