Java基础巩固——排序

快速排序

基本思想：

　　通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对两部分继续进行排序，直到整个序列有序。

 

实例：

1.一趟排序的过程：

2.排序的全过程：

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比他小，则交换，比它大不做任何处理；

交换了以后再和小的那端比，比它小不交换，比它大交换。这样循环往复，一趟排序完成，左边的就是比中轴小的，

右边的就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。

 

代码实现

public class QucikSortDemo {
    public static void main(String arg[]) {

        int[] numbers = {10, 89, 87, 76, 56, 46, 11, 75, 32, 35, 98};
        System.out.println("排序前：");
        printArr(numbers);

        quickSort(numbers);
        System.out.println("排序后：");
        printArr(numbers);
    }

    /**
     * 查找出中轴位置(默认是最低为low)的在number数组排序后所在位置
     *
     * @param numbers
     * @param low
     * @param high
     * @return
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        // 数组的第一位作为中轴
        int temp = numbers[low];
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            // 比中轴晓得记录移动到低端
            numbers[low] = numbers[high];
            while (low < high && numbers[low] < temp) {
                low++;
            }
            // 比中轴大的记录移到高端
            numbers[high] = numbers[low];

        }
        // 中轴记录到尾
        numbers[low] = temp;
        // 返回中轴的位置
        return low;
    }

    /**
     * 分治排序
     *
     * @param numbers
     * @param low
     * @param high
     */
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            // 将numbers数组进行一分为二
            int middle = getMiddle(numbers, low, high);
            // 将低字段表进行递归排序
            quickSort(numbers, low, middle - 1);
            // 将高字段表进行递归排序
            quickSort(numbers, middle + 1, high);
        }
    }

    public static void quickSort(int[] numbers) {
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
    }

    public static void printArr(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + ",");
        }
        System.out.println("");
    }

}