插入排序

插入排序通过构建有序序列，对于未排序的数据，从已排序的序列从后向前扫描，并找到相应的位置插入。

算法描述

1. 从第一个元素开始，默认第一个元素已排序；
2. 取出下一个元素i，从已排序的元素序列中从后向前扫描；
3. 对比每一个已排序的元素，将大于(小于)改元素的已排序元素向后移一个位置直到找到小于(大于)该元素的位置，将i 排在这个元素的后面；
4. 重复2-3直到遍历结束，排序完成；

代码实现

public void sort(int[] arr, int n) {
    for(int i = 1;i < n; i++) {
        for(j = i+1; j > 0; j--) {
            if(arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = arr[j];
            }
        }
    }
}