快速排序算法分析与实现

基本思路

使用分治思想。选择一个Pivot，把小于Pivot的放到Pivot左边，大于Pivot的放到Pivot右边。之后继续对Pivot分隔开的左右两侧做相同的操作，直到所有元素有序。

复杂度

这里讨论的是原地算法的复杂度。

1、最好的情况下，每次选取的Pivot，都能把数组平分为两部分，时间复杂度为 O(N·logN)，空间复杂度为O(logN)。

2、最坏的情况下，每次选取的Pivot，都是最大值（最小值），每次只能排好一个元素，退化为冒泡排序，时间复杂度为 O(N^2)，空间复杂度为O(N)。

总结：

• 时间复杂度：最好：O(N·logN)，最坏：O(N^2)，平均：O(N·logN)
• 空间复杂度：最好：O(logN)，最坏：O(N)

具体的推导过程可以参考：https://blog.csdn.net/YuZhiHui_No1/article/details/44198701

Pivot选择

Pivot的选择是快速排序的关键，对复杂度起到决定作用。Pivot的选择有很多种，例如：

• 选第一个
• 选最后一个
• 选中间一个
• 随机选一个
• 三数取中法

为了便于算法实现，需要取中间某个Pivot时，可以通过交换元素，转换成取第一个（或最后一个）。

随机选取

使用Random随机选一个，并交换到开头。

static void movePivotToStart(int[] array, int start, int end) {
    // 随机选一个作为pivot并移动到开头
    int pivotIndex = start + new Random().nextInt(end - start);
    swap(array, pivotIndex, start);
}

其中swap是通用的元素交换方法：

static void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}

三数取中法

三数取中法的策略是，分别取开头、末尾和中间三个数，并将值处于中间的那个数作为Pivot。

代码实现如下，利用类似冒泡排序的思路，将start,mid,end按照从小到大的顺序排列起来。然后再把中间值即mid交换到start。

static void movePivotToStart(int[] array, int start, int end) {
    int mid = (start + end) / 2;
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    if (array[mid] > array[end]) {
        swap(array, mid, end);
    }
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    swap(array, start, mid);
}

因为最后两步可能会对start和mid进行两次交换，还可以进一步优化为：

static void movePivotToStart(int[] array, int start, int end) {
    int mid = (start + end) / 2;
    if (array[start] > array[mid]) {
        swap(array, start, mid);
    }
    if (array[mid] > array[end]) {
        swap(array, mid, end);
    }
    if (array[start] <= array[mid]) {
        swap(array, start, mid);
    }
}

非原地算法

快排又分为非原地排序和原地排序。非原地排序思路很简单，但是给数组排序需要消耗额外内存。这个思路更适合链表排序。伪代码如下（来自维基百科 ）：

function quicksort(q)
{
    var list less, pivotList, greater
    if length(q) ≤ 1
    return q
    else {
        select a pivot value pivot from q
        for each x in q except the pivot element {
            if x < pivot then add x to less
            if x ≥ pivot then add x to greater
        }
        add pivot to pivotList
        return concatenate(quicksort(less), pivotList, quicksort(greater))
    }
}

原地算法partition实现

通常会把选取pivot和移动元素的操作放到partition方法中，而partition有多种实现。

static void quickSort(int[] array, int start, int end) {
    // start = end时，size为1，不需要排序
    if (start >= end) {
        return;
    }
    // 处理并返回pivot
    int index = partition(array, start, end);
    quickSort(array, start, index - 1);
    quickSort(array, index + 1, end);
}

实现一：遍历

最常见的实现，选第一个作为Pivot，然后直接从左到右遍历，把数据分割为两部分。

static int partition(int[] array, int start, int end) {
    // 取第一个作为轴
    int pivot = array[start];

    // index为pivot最终的位置，最终要满足 [start~index-1] < [index] < [index+1 ~ end]
    int index = start;

    // 循环过程中，先不移动pivot，满足 [start+1 ~ index] < pivot < [index+1 ~ end]
    for (int i = start + 1; i <= end; i++) {
        if (array[i] < pivot) {
            index++;
            swap(array, index, i);
        }
    }

    // 最终交换 start 和 index，让pivot移动到正确的位置，
    // 使得 [start~index-1] < [index] < [index+1 ~ end]
    swap(array, start, index);
    return index;
}

对应的示意图如下：

参考： https://www.cnblogs.com/onepixel/p/7674659.html

实现二：两端搜索交换

选中最后一个作为Pivot，先从左边找到第一个大于Pivot的元素，再从右边找到第一个小于Pivot的元素，将这两者交换。继续交互步骤直到两端相遇。

或者：选中第一个作为Pivot，先从右边找到第一个小于Pivot的元素，再从左边找到第一个大于Pivot的元素，将这两者交换。

注意选中一端作为Pivot，就必须先从另一端搜索，因为可能会有一个特殊情况，就是原始数组已经满足条件不需要调整。

static int partition(int[] array, int start, int end) {
    int pivot = array[start];

    // 这里有一种特殊情况，
    // 原始数组已经满足 [start] < [start+1 ~ end]，执行循环后，应该得到 i = j = start

    // i必须从start开始，而不是 start + 1
    int i = start, j = end;
    while (i < j) {
        // 必须先执行--j的操作
        while (i < j && array[j] >= pivot) --j;
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            swap(array, i, j);
        }
    }
    // 移动pivot到正确位置
    swap(array, start, i);
    return i;
}

图片示意：

还可以参考：https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

顺便把图片摘录过来了：

实现三：挖坑法

挖坑法。选取第一个作为Pivot，并挖出来形成一个坑。先从右边找到第一个小于Pivot的元素，挖出来填到坑里。再从左边找到第一个大于Pivot的元素，挖出来填到坑里。继续填坑步骤直到两端相遇。

static int partition3(int[] array, int start, int end) {
    int pivot = array[start];
    // [start] 是第一个坑
    int i = start, j = end;
    while (i < j) {
        while (i < j && array[j] >= pivot) --j;
        if (i < j) {
            // [j] 挪到 [i] , [j] 形成了新的坑
            array[i] = array[j];
            ++i;
        }
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            // [i] 挪到 [j] , [i] 形成了新的坑
            array[j] = array[i];
            --j;
        }
    }
    //退出时，i == j。将 pivot 填到这个坑中。
    array[i] = pivot;
    return i;
}

参考： https://blog.csdn.net/MoreWindows/article/details/6684558

总结：快排完整写法示例

下面给出一个快排完整示例，Pivot使用随机选取，两端搜索交换。

static void quickSort(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partition(array, start, end);
    quickSort(array, start, pivot - 1);
    quickSort(array, pivot + 1, end);
}

static int partition(int[] array, int start, int end) {
    movePivotToStart(array, start, end);
    int pivot = array[start];
    int i = start, j = end;
    while (i < j) {
        while (i < j && array[j] >= pivot) --j;
        while (i < j && array[i] <= pivot) ++i;
        if (i < j) {
            swap(array, i, j);
        }
    }
    swap(array, start, i);
    return i;
}

static void movePivotToStart(int[] array, int start, int end) {
    int pivotIndex = start + new Random().nextInt(end - start);
    swap(array, pivotIndex, start);
}

static void swap(int[] array, int x, int y) {
    int tmp = array[x];
    array[x] = array[y];
    array[y] = tmp;
}