/**
 * 排序算法
 * Created by littlejie on 2017/2/6.
 */
public class Sort {

    //1，2，3，3，4，5，7，8，9
    public static final int[] SORT_ARRAY = {1, 9, 5, 3, 3, 4, 2, 8, 7};

    public static void main(String[] args) {
        bubbleSort(SORT_ARRAY);
    }

    /**
     * 冒泡排序
     *
     * @param array
     */
    private static void bubbleSort(int[] array) {
        int temp;//临时变量
        boolean flag;//排序过程中是否发生交换
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            flag = false;
            for (int j = length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    flag = true;
                }
            }
            if (!flag) break;
        }
    }

    /**
     * 选择排序
     *
     * @param array
     */
    private static void selectSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            int temp;
            int minIndex = i;//保存最小值索引
            //寻找第 i 个最小数
            for (int j = i + 1; j < length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
            printArray(array);
        }
    }

    /**
     * 插入排序
     *
     * @param array
     */
    private static void insertSort(int[] array) {
        int length = array.length;
        //插入排序，第一位肯定有序的，所以从第二个开始
        for (int i = 1; i < length; i++) {
            int temp = array[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置

            // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
            int j = i - 1;
            for (; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = temp;
            printArray(array);
        }
    }

    private static void printArray(int[] array) {
        System.out.println(Arrays.toString(array));
    }
}