package limeMianShi;

import java.util.Arrays;

/**
 * 设有一组关键字｛K1， K2，…， Kn｝；
 * 
 * 排序开始就认为 K1 是一个有序序列；让 K2 插入上述表长为 1 的有序序列，使之成为一个表长为 2的有序序列；
 * 
 * 然后让 K3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；
 * 
 * 依次类推，最后让 Kn 插入上述表长为 n-1的有序序列，得一个表长为 n 的有序序列。
 * 
 * 具体算法描述如下：
 * 
 * 1.从第一个元素开始，该元素可以认为已经被排序
 * 
 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 
 * 4.重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
 * 
 * 5.将新元素插入到该位置后
 * 
 * 6.重复步骤 2~5
 * 
 * @author lime
 *
 */
public class Insertion_Sort {

    public static void main(String[] args) {
        int[] insertion = new int[10];
        for (int i = 0; i < insertion.length; i++) {
            insertion[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(insertion) + " 原始数据");
        // BaseDo(insertion);
        minusTimesDo(insertion);
        System.out.println(Arrays.toString(insertion) + " 序列数据");
    }

    private static void minusTimesDo(int[] insertion) {
        int times = insertion.length;
        for (int i = 1; i < times; i++) {
            int temp = insertion[i];
            for (int j = i; j >= 0; j--) {
                System.out.println(Arrays.toString(insertion) + " i = " + i + " j = " + j);
                if(j == 0){
                    insertion[j] = temp;
                    break;
                }
                if (insertion[j - 1] > temp) {
                    insertion[j] = insertion[j - 1];
                } else {
                    insertion[j] = temp;
                    break;
                }
            }
            System.out.println("---");
        }
    }

    private static void BaseDo(int[] insertion) {
        int times = insertion.length;
        for (int i = 1; i < times; i++) {
            for (int j = i; j > 0; j--) {
                System.out.println(Arrays.toString(insertion) + " i = " + i + " j = " + j);
                if (insertion[j - 1] > insertion[j]) {
                    ArrayUtil.swap(insertion, j - 1, j);
                } else {
                    break;
                }
            }
            System.out.println("---");
        }
    }
}