快速排序(Quick Sort)

快速排序(Quick Sort) 是基于二分法的一种排序方式,基本思路是:在需要排序的元素中,任意选一个元素作为基准元素,比该元素大的,排在该元素右边,其余排在左边,排好后,再对该元素左右两侧以同样的方式排序,直至全部排完。

在一般编程实践中,基准元素就选第一个元素。具体代码一般通过递归完成,因为使用语言和个人习惯不同,代码实现也可能并不一样。

举例:将7, 9, 3, 2, 5, 1, 8这几个整数,按升序(从小到大)排列。

用快速排序的过程如下:

quick sort

代码

相关代码如下:

(参:http://git.oschina.net/iridiumcao/iridiumonline/blob/master/helloalgorithm/src/main/java/info/iridiumcao/algorithm/sorting/QuickSort.java

public class QuickSort3 {
    private static Scanner scanner;

    public static void main(String[] args) {
        System.out.println("Please input integers split by comma (do not input blank): ");
        scanner = new Scanner(System.in);
        String sc = scanner.next();
        String[] ints = sc.split(",");
        int[] arrays = new int[ints.length];
        for (int i = 0; i < ints.length; i++) {
            arrays[i] = Integer.parseInt(ints[i]);
            // System.out.println(arrays[i]);
        }
        QuickSort3 qs = new QuickSort3();
        qs.quickSort(arrays, 0, arrays.length - 1);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(arrays[i] + ", ");
        }
    }

    // 把基准值放到合适的位置后,并返回基准值的 index
    public int moveBase(int[] list, int left, int right) {
        if (list.length == 1 || left == right) {
            return left;
        }
        int baseIndex = left;
        int base = list[baseIndex]; // 数组的第一个作为基准值
        while (left + 1 < right) { // 这里比较的是哨兵的 index,左边哨兵的 index = left + 1
            while (left + 1 < right && list[right] >= base) {
                right--;
            }
            while (left + 1 < right && list[left + 1] <= base) {
                left++;
            }
            int tmp = list[left + 1];
            list[left + 1] = list[right];
            list[right] = tmp;
        }
        // 交换基准值和 left 哨兵位置的值
        list[baseIndex] = list[left + 1];
        list[left + 1] = base;
        return left + 1; // 返回基准值的 index
    }

    /**
     * @param list  array
     * @param left  left index
     * @param right right index
     */
    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            int baseIndex = moveBase(list, left, right); // 将 list 数组进行一分为二
            quickSort(list, left, baseIndex - 1); // 对左边的元素排序
            quickSort(list, baseIndex + 1, right); // 对右边的元素排序
        }
    }
}

以上代码需要注意,先使用 r 哨兵探测,然后再使用 l 哨兵。如果要先使用 l 探,再使用 r 探,不是不可以,但程序需要再重新。这里不再描述此问题。可以思考,对 3, 1, 2, 5, 4 如果选择3为基准量,然后从左边先探得到的结果。

其他:pzhtpf from CSDN 的办法

在前几天研究快速排序代码实现时,在 CSDN 上发现 pzhtpf 是这样实现的:

// 将基准量移动到合适的位置,并返回基准值的 index 
public int getMiddle(int[] list, int low, int high) {
    int tmp = list[low]; // 数组的第一个作为中轴
    while (low < high) {
        while (low < high && list[high] >= tmp) { // 从右往左扫描,探测比基准量小的元素
            high--;
        }
        list[low] = list[high]; // 比中轴小的记录移到低端
        while (low < high && list[low] <= tmp) { // 从左往右扫描,探测比基准量大的元素
            low++;
        }
        list[high] = list[low]; // 比中轴大的记录移到高端
    }
    list[low] = tmp; // 中轴记录到尾
    return low; // 返回中轴的位置
}

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

注意,代码中的「中轴」,即「基准量」,代码来源于本页「参考」部分的链接,写得比较有技巧,但效率不太优。它将左哨兵设置到基准量上,导致了一个多余的比较操作,同时,它的左边移动到右边,右边再移动左边往右的方式,有很强的技巧性,理解起来也不够直观。虽然如此,它的代码仍然给我启发。这部分代码对第一个值归位的图示如下:

quick sort from csdn

由上图可见,基准值归位移动的次数比较多。更好的方式是基准量不再探测,可以参见本文的第一个实现。

参考:

http://blog.csdn.net/pzhtpf/article/details/7560294 程序员必知的8大排序(三)-------冒泡排序,快速排序(java实现, by pzhtpf)