排序

1. 冒泡排序

        int temp;
        boolean flag = true;
        for (int i = 0; i < arr.length && flag; i++) {
            flag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
        }

2. 快速排序

     /**
     * 快速排序
     *
     * @param array 待排序数组
     * @param low   排序最小索引
     * @param high  排序最大索引
     */
    private static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            //获取中轴位置
            int pivot = getPartition(array, low, high);
            //对中轴左侧元素递归排序
            quickSort(array, low, pivot - 1);
            //对中轴右侧元素递归排序
            quickSort(array, pivot + 1, high);
        }
    }
    /**
     * 获取中轴位置
     *
     * @param array 待排序数组
     * @param low   排序最小索引
     * @param high  排序最大索引
     * @return
     */
    private static int getPartition(int[] array, int low, int high) {
        //默认第一个元素作为key
        int temp = array[low];
        while (low < high) {
            //从最大元素开始依次比较，将大于或等于key的元素放到右边
            while (low < high && array[high] >= temp) {
                high--;
            }
            array[low] = array[high];
            //从最小元素开始依次比较，将小于key的元素放到左边
            while (low < high && array[low] < temp) {
                low++;
            }
            array[high] = array[low];
        }
        //关键元素放回数组
        array[low] = temp;
        return low;
    }