排序算法（一）插入排序

插入排序基本思想是将一个元素插入到已经排好序的元素序列中，其中前面n-1个元素都是排好序的，现将第n个元素与前面n-1个元素倒序（第n-1个元素 -> 第1个元素）依次对比，直至找到第n个元素的位置。

复杂度分析

最好情况下，需要排序的序列本身就是有序的，此时只有数据比较，没有数据移动，时间复杂度为O(n)。
最坏情况下，需要排序的序列是完全逆序的，时间复杂度为O(n²)。
平均时间复杂度为O(n²)。

Java 代码实现

import java.util.Arrays;

public class InsertionSort {

    public static void sort(int[] a) {
        // 从第2个元素开始遍历
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0 && a[j] - a[j - 1] < 0; j--) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                System.out.println(Arrays.toString(a));
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {34, 24, 93, 1, 32, 98, 18, 39};
        sort(a);
    }
}

运行结果

[24, 34, 93, 1, 32, 98, 18, 39]
[24, 34, 1, 93, 32, 98, 18, 39]
[24, 1, 34, 93, 32, 98, 18, 39]
[1, 24, 34, 93, 32, 98, 18, 39]
[1, 24, 34, 32, 93, 98, 18, 39]
[1, 24, 32, 34, 93, 98, 18, 39]
[1, 24, 32, 34, 93, 18, 98, 39]
[1, 24, 32, 34, 18, 93, 98, 39]
[1, 24, 32, 18, 34, 93, 98, 39]
[1, 24, 18, 32, 34, 93, 98, 39]
[1, 18, 24, 32, 34, 93, 98, 39]
[1, 18, 24, 32, 34, 93, 39, 98]
[1, 18, 24, 32, 34, 39, 93, 98]