package sort;

/**
 * Created by ozc on 2018/3/15.
 *
 * @author ozc
 * @version 1.0
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arrays = {9, 8, 1, 4, 2, 3, 5, 6, 7, 13, 12, 14, 11, 15, 16, 17, 19, 18, 10};

        sort2(arrays);

        System.out.println(arrays);
    }


    /**
     * 
     * @param arrays
     */
    public static void sort(int[] arrays) {

        //int[] arrays = {3, 2, 1, 3, 3};


/*        //--------------------
        int temp;
        if (arrays[1] > arrays[0]) {
            //

        } else {
            //()
            temp = arrays[1];
            arrays[1] = arrays[0];
            arrays[0] = temp;

        }

        System.out.println("Java3y" + arrays);

        //--------------------

        if (arrays[2] > arrays[1]) {
            //

        } else {
            //
            temp = arrays[2];
            arrays[2] = arrays[1];

            //
            if (temp > arrays[0]) {
                arrays[1] = temp;
            } else {

                //
                int swapTemp = arrays[0];
                arrays[0] = temp;
                arrays[1] = swapTemp;

            }

        }
        System.out.println("Java3y" + arrays);*/


        //
        int temp;


        //(10)
        for (int i = 1; i < arrays.length; i++) {

            temp = arrays[i];

            //()[]
            int j = i - 1;

            while (j >= 0 && arrays[j] > temp) {

                //
                arrays[j + 1] = arrays[j];

                //
                j--;

            }
            //
            arrays[j + 1] = temp;

        }
        System.out.println("Java3y" + arrays);
    }


    /**
     * :index
     * @param arrays
     */
    public static void sort2(int[] arrays) {


        //
        int temp;


        //(10)
        for (int i = 1; i < arrays.length; i++) {


            //
            int index = BinarySearchIndex(arrays, i - 1, arrays[i]);


            //
            if (index != i) {

                temp = arrays[i];

                int j;

                // arr[index]
                for (j = i - 1; j >= index && j >= 0; j--) {

                    arrays[j + 1] = arrays[j];

                }
                arrays[j + 1] = temp;
            }

        }
        System.out.println("Java3y" + arrays);
    }


    private static int BinarySearchIndex(int[] arr, int maxIndex, int data) {

        // 
        int left = 0;
        int right = maxIndex;
        int mid;


        //
        while (left = arr[mid]) {

                //--->+1
                left = mid + 1;
            } else {
                //
                right = mid - 1;
            }
        }

        //..
        return left;
    }

}