快速排序-白红宇

快速排序

基本思想：

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

实例：

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("");    }}