package jt.test;

public class SortUtil {
    /**
     * 交换数组中i和j的位置
     *
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static boolean lt(int x, int y) {
        return x < y;
    }

    private static boolean gt(int x, int y) {
        return x > y;
    }

    /**
     * 输出数组结果
     *
     * @param array
     */
    public static void printArrays(int[] array) {
        for (int num : array) {
            System.out.print(num);
            System.out.print(' ');
        }
    }

    /**
     * 冒泡法排序
     *
     * @param array
     */
    public static void BubbleSort(int[] array) {
        int count = array.length;
        if (count == 0) {
            return;
        }
        boolean noSwap = false;
        for (int i = 1; i < count; i++) {
            noSwap = true;
            for (int j = count - 1; j >= i; j--) {
                if (lt(array[j], array[j - 1])) {
                    swap(array, j, j - 1);
                    noSwap = false;
                }
            }

            if (noSwap) {
                return;
            }
        }
    }

    /**
     * 选择法排序
     *
     * @param array
     */
    public static void SelectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int smallest = i;
            for (int j = i + 1; j < array.length; j++) {
                if (lt(array[j], array[smallest])) {
                    smallest = j;
                }
            }
            swap(array, i, smallest);
        }
    }

    /**
     * 插入法排序
     *
     * @param array
     */
    public static void InsertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i;
            while (j > 0 && array[j - 1] > tmp) {
                array[j] = array[j - 1];
                --j;
            }
            array[j] = tmp;
        }
    }

    /**
     * 希尔排序
     *
     * @param array
     */
    public static void ShellSort(int[] array) {
        for (int gap = array.length / 2; gap > 0; gap /= 2)
            for (int i = gap; i < array.length; i++)
                for (int j = i - gap; j >= 0; j -= gap)
                    if (gt(array[j], array[j + gap]))
                        swap(array, j, j + gap);

    }

    /**
     * 快速排序
     *
     * @param array
     * @param left
     * @param right
     */
    public static void QuickSort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    /**
     * 快速排序算法
     *
     * @param array
     * @param left
     * @param right
     */
    private static void sort(int[] array, int left, int right) {
        int i = left, j = right;
        int middle = array[(left + right) / 2];
        do {
            while (lt(array[i], middle) && lt(i, right))
                i++;
            while (gt(array[j], middle) && gt(j, left))
                j--;
            if (i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }

        } while (i <= j); // 如果两边扫描的下标交错，就停止（完成一次）


        if (lt(left, j))
            sort(array, left, j);
        if (gt(right, i))
            sort(array, i, right);
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] a = new int[] { 2, 4, 1, 67, 8, 50, 89, 34, 68, 4, 45 };
        // BubbleSort(a);

        // SelectSort(a);

        // InsertSort(a);

        // ShellSort(a);

        QuickSort(a);
        printArrays(a);
    }
}