快速排序

快速排序

快速排序的时间复杂度为O(n2)，但其平均性能很好，其期望复杂度为O(nlog2n)，并且其中隐含的常数因子很小。

对输入数组A[p..r]，将其划分为两个子数组A[p..q-1]和A[q+1..r]，其中A[q]满足，A[q]大于等于任意一个属于A[p..q-1]的元素，小于等于任意一个属于A[q+1..r]的元素。递归划分左右两个子数组，最终就可以得到排序后的数组。其算法如下：

    sort(array)
        sort(array, 0, array.length-1)
    
    sort(array, start, end)
        if start < end
            q = partition(array, start, end)
            sort(array, start, q-1)
            sort(array, q+1, end)

其中partition分解过程中找到q的位置，其算法如下：

    partition(array, start, end)
        i = start - 1
        for j = start to end-1
            if array[j] <= array[end]
                i++
                if i != j
                    exchange array[i] with array[j]
        i++
        exchange array[i] with array[end]
        return i

partition算法解析：

(1)将最后一个元素作为主元，由于最开始待划分的两个子数组的大小为0，因此定义分隔位置i的值为start-1，i表示第一个子数组的最后一个元素，而i+1表示分隔的位置。
(2)围绕主元对start和end-1内的元素进行划分，如果小于等于主元，第一个子数组的大小加1，即分隔位置加1。此时由于a[j]小于主元，因此将其交换到i指示的位置。
(3)最后，分隔位置加1，此时为第二个数组的第一个位置，将其与主元交换后，这个位置就变成了正确的分隔位置。
这样在每一次执行partition之后，所有i左侧的元素均小于等于array[i]，i右侧的元素大于等于array[i]，而array[i]找到了它在数组中的正确位置。

实例的推导过程(参考《算法导论 第三版》)如下图:

java实现

package com.diysoul.algorithm.sort;

import java.util.Random;

public class QuickSort {

    public static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int start, int end) {
        if (start < end) {
            int p = partition(array, start, end);
            sort(array, start, p - 1);
            sort(array, p + 1, end);
        }
    }

    public static int partition(int[] array, final int start, final int end) {

        // 增加随机主元，仅测试
        // Random random = new Random();
        // int pos = random.nextInt(end - start + 1) + start;
        // if (pos != end) {
        // int temp = array[end];
        // array[end] = array[pos];
        // array[pos] = temp;
        // }

        int i = start - 1;
        for (int j = start; j <= end - 1; j++) {
            if (array[j] <= array[end]) {
                i++;
                if (i != j) {
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        i++;
        int temp = array[i];
        array[i] = array[end];
        array[end] = temp;
        return i;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int min = -10000;
        int max = 10000;
        Random random = new Random();

        int[] a = new int[maxSize];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(max - min) + min;
        }
        
        print(a);
        sort(a);
        print(a);
        checkSort(a);
    }

    private static void checkSort(int[] array) {
        if (array == null || array.length == 0)
            return;
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) {
                System.out.println("Error! Array is not sorted in index " + i);
                break;
            }
        }
    }

    private static void print(int[] array) {
        if (array == null || array.length == 0)
            return;
        System.out.print("quick sort array(" + array.length + "): ");
        int i = 0;
        for (; i < array.length - 1; i++) {
            System.out.print(array[i] + ", ");
        }
        System.out.println(array[i]);
    }
}