插入排序-Insertion Sort

插入排序是一种比较简单的排序方法，又被称作直接插入排序。

基本思想：设待排序数据元素个数为N

实现步骤

将待排序数据分为两部分，有序区和无序区。
1，首先，默认有序区为第一个元素，其他为无序区。
2，从无序区提取首个元素A，和有序区中元素依次进行比较，如果A小，有序区中当前元素后移，A往前移，再次比较前一个元素：如果A大，就保持不变。此时形成新的有序区和无序区。（有序区中元素数量加1，无序区中元素数量减一）
3，其次，继续上一个步骤，直到无序区中元素数量为0
4，最后，完成排序。

排序代码：

public void insertionSort() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int length = befArrays.length;

    for (int i=1; i<length; i++) {
        for (int j=i; j>0; j--) {
            if (befArrays[j] < befArrays[j-1]) {
                int swap = befArrays[j-1];
                befArrays[j-1] = befArrays[j];
                befArrays[j] = swap;
            } else {
                break;
            }
        }
    }

    for (int i=0; i<length; i++) {
        System.out.printf(befArrays[i] + "\t");
    }
}

算法分析：

概述，插入算法比较简单。效率一般，算法的平均复杂度是O(n²)，相比其他排序算法，复杂度较高。