/**
 * 直接插入排序
 * @author TMAC-J
 * 思路：详情见百度百科，解释的很清楚
 * 这里没有对向后移动做优化，有兴趣的可以自己做做
 *
 */
public class InsertSort {
    
private int[] array;
    
    public InsertSort(int[] array) {
        this.array = array;
    }
    /**
     * 按从小到大的顺序排列
     */
    public void calculate(){
        for(int i = 1;i<array.length;i++){
            for(int j = 0;j<i;j++){
                if(array[i]<array[j]){
                    int temp = array[i];
                    //向后移动
                    for(int k = i-1;k>=j;k--){
                        array[k+1] = array[k];
                    }
                    array[j] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] a = {10,9,8,7,6,5,4,3,2,1};
        InsertSort insertSort = new InsertSort(a);
        insertSort.calculate();
        for(int i = 0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    
}