Quick Sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

图解

详解

白话经典算法系列之六快速排序快速搞定
 快速排序的三种实现方式以及非递归版本
 快速排序最好，最坏，平均复杂度分析
 快速排序最坏的情况啥时候出现？
马士兵说：分析快速排序的时间复杂度和空间复杂度
 [数据结构与算法] 排序(三) 平均时间复杂度O(nlogn)
14.7 快速排序
 归并排序的空间复杂度为什么是O（n）？快速排序的空间复杂度为什么是O（log2n）？
快排及时间复杂度简单证明

标准写法（递归版本）

交换左右指针法
交换前后指针法
填坑法

上面的的3种方法的主要区别在于partition分区时的操作

交换左右指针法的partition分区

public static int partition(int[] arr, int left, int right) {

    // pivot的位置可以在开头，也可以在最后，也可以在随机位置
    // 标准写法是在开头或最后
    // pivot在开头的写法
    int pivot = arr[left];
    // 定义两个指针：左指针begin和右指针end，左指针在pivot后面
    int begin = left + 1;
    int end = right;
    // pivot在最后的写法
    // int pivot = arr[right];
    // 定义两个指针：左指针begin和右指针end，右指针在pivot前面
    // int begin = left;
    // int end = right - 1;

    // 比pivot小的值都移动到pivot左边
    // 比pivot大的值都移动到pivot右边
    while (begin < end) {
        // 若当前值 <= pivot，左指针向左移动
        // 移动直到当前值 > pivot时停下
        // 或begin == end时停下
        while (begin < end && arr[begin] <= pivot) {
            begin++;
        }
        // 若当前值 > pivot，右指针向右移动
        // 移动直到当前值 < pivot时停下
        // 或begin == end时停下
        while (begin < end && arr[end] >= pivot) {
            end--;
        }
        // begin == end时不交换
        if (begin < end) {
            swap(arr, begin, end);
        }
    }

    // 最后需要把指针的位置的值和 begin与end重合后的位置 的位置的值交换
    // pivot在开头的写法
    // 两种特殊情况
    // 1. begin一直向右移动，如果begin一直没有找到大于left(pivot)的值，会停在end(right)的位置
    // 此时begin与end重合，left(pivot)后面的值都比left(pivot)小
    // 2. end一直向左移动，如果end一直没有找到小于left(pivot)的值，会停在left(pivot)的后一个位置
    // 此时begin与end重合，left(pivot)后面的值都比left(pivot)大
    // 除去两种特殊情况，执行下面代码
    if (left != end - 1 && right != end) {
        swap(arr, left, end - 1);
    } else {
        // 对于两种特殊情况，left(pivot)和end交换
        if (pivot > arr[end]) {
            swap(arr, left, end);
        }
    }
    // 返回pivot的位置
    return end - 1;

    // pivot在最后的写法
    // 两种特殊情况
    // 1. begin一直向右移动，如果begin一直没有找到大于right(pivot)的值，会停在right(pivot)的前一个位置
    // 此时begin与end重合，right(pivot)前面的值都比right(pivot)小
    // 2. end一直向左移动，如果end一直没有找到小于right(pivot)的值，会停在begin(left)的位置
    // 此时begin与end重合，right(pivot)后面的值都比right(pivot)大
    // 除去两种特殊情况（2无影响），执行下面代码
    // if (arr[begin] > arr[right]) {
    //     swap(arr, begin, right);
    // }
    // 返回pivot的位置
    // return begin;
}

交换前后指针法的partition分区

public static int partition(int[] arr, int left, int right) {

    // pivot的位置可以在开头，也可以在最后，也可以在随机位置
    // 标准写法是在开头或最后
    // pivot在开头的写法
    int pivot = arr[left];
    // 定义两个指针：前指针prev和后指针cur，后指针在pivot的位置
    int prev = left;
    int cur = left + 1;
    // pivot在最后的写法
    // int pivot = arr[right];
    // 定义两个指针：前指针prev和后指针cur，后指针在left前面，即当前区间外
    // int prev = left - 1;
    // int cur = left;

    // 比pivot小的值都移动到pivot左边
    // 比pivot大的值都移动到pivot右边
    while (cur < right) {
        // 后指针cur指向的值小于pivot时
        if (arr[cur] < pivot) {
            // 前指针prev前移一格
            prev++;
            // 若前指针prev和后指针cur没有重合，则交换前后指针的元素
            if (prev != cur) {
                swap(arr, prev, cur);
            }
        }
        cur++;
    }

    // pivot在开头的写法
    // 最后当后指针cur移动到right时
    // 此时需要前指针prev的元素和left(pivot)交换
    // 两种特殊情况
    // 1. 若此时前指针prev到达right的前一格
    // 则代表right前面的值都是比right小，若pivot也比right小，则无需交换
    // 2. 若此时前指针prev的元素的值 <= pivot，则无需交换
    if (prev == cur - 1) {
        if (arr[right] < pivot) {
            swap(arr, left, right);
        }
    } else {
        if (arr[prev] > pivot) {
            swap(arr, left, prev);
        }
    }
    // 返回pivot的位置
    return prev;

    // pivot在最后的写法
    // 最后当后指针cur移动到right(pivot)时
    // 此时需要前指针prev的后一格的元素和right(pivot)交换
    // 两种特殊情况
    // 1. 若此时前指针prev到达right(pivot)的前一格
    // 则代表right(pivot)前面的值都是比right(pivot)小，则无需交换
    // 2. 若此时前指针prev的后一格的元素的值 <= pivot，则无需交换
    // prev++;
    // if (prev == cur) {
    //     // 返回pivot的位置
    //     return prev - 1;
    // } else {
    //     if (arr[prev] > pivot) {
    //         swap(arr, prev, right);
    //     }
    //     // 返回pivot的位置
    //     return prev;
    // }
}

填坑法的partition分区

public static int partition(int[] arr, int left, int right) {

    // pivot的位置可以在开头，也可以在最后，也可以在随机位置
    // 标准写法是在开头或最后
    // 注意：pivot在开头的写法和在最后的写法差异较大
    // 规则是：在下面的while循环中，pivot在开头时，先移动右指针；pivot在最后时，先移动左指针

    // pivot在最后的写法
    int pivot = arr[right];
    // 定义两个指针：左指针begin和右指针end，注意end从right开始
    int begin = left;
    int end = right;

    // 比pivot小的值都移动到pivot左边
    // 比pivot大的值都移动到pivot右边
    while (begin < end) {
        // 若当前值 <= pivot，左指针向左移动
        // 移动直到当前值 > pivot时停下
        // 或begin == end时停下
        while (begin < end && arr[begin] <= pivot) {
            begin++;
        }
        // 此时当前值 > pivot，把当前值赋值到arr[end]
        // 把比pivot大的值都往右边移动
        if (begin < end) {
            arr[end] = arr[begin];
        }
        // 若当前值 > pivot，右指针向右移动
        // 移动直到当前值 < pivot时停下
        // 或begin == end时停下
        while (begin < end && arr[end] >= pivot) {
            end--;
        }
        // 此时当前值 < pivot，把当前值赋值到arr[end]
        // 把比pivot小的值都往左边移动
        if (begin < end) {
            arr[begin] = arr[end];
        }
    }

    // pivot在最后的写法
    // 两种特殊情况
    // 1. begin一直向右移动，如果begin一直没有找到大于right(pivot)的值，会停在right(pivot)的位置
    // 此时begin与right(pivot)重合，right(pivot)后面的值都比right(pivot)小，返回right(pivot)前面的元素的位置
    // 2. end一直向左移动，如果end一直没有找到小于left(pivot)的值，会停在left(begin)的后一个位置
    // 此时begin与end重合，left(begin)后面的值都比left(begin)大，不需要特殊考虑
    if (begin != right) {
        arr[end] = pivot;
        return end;
    } else {
        return end - 1;
    }
}

递归思想，先对代码分区（分成两个部分），再分别进行快速排序

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

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot);
        quickSort(arr, pivot + 1, right);
    }
}

交换数组中的两个元素

public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

快速排序的优化以及各种版本及来由

根据直观含义得到普通快速排序：从左到右或从右到左的单向扫描。设立两个区：小于区，大于等于区

普通快速排序的问题：

问题1：对于渐进有序的数组，效率很差
- 改进为随机选择pivot：把得到的pivot和数组的开头或最后的元素交换，得到随机化快速排序
问题2：对于含有大量重复元素的数组，即使是随机化快排效率也很差
- 改进为双路快排：从两端向中间挺近，设立两个区：小于等于区，大于等于区（上面的几个写法都是属于双路快排，从while循环中arr[begin] <= pivot和arr[end] >= pivot可以看出，等于pivot的数在两边均有分布，避免集中在一边，从而克服了不平衡问题）
- 改进为三路快排：从两端向中间挺近，设立三个区：小与区，等于区，大于区

问题1的改进代码

public static int partition(int[] arr, int left, int right) {

    // 在开头加入以下代码产生随机pivot，把得到的pivot和数组的开头或最后的元素交换
    Random rand = new Random();
    int interval = right - left + 1;
    int randPivotIndex = rand.nextInt(interval) + left;
    swap(arr, randPivotIndex, left);

    // 下面代码不用改动...
}

问题2的改进代码

// 三路快排中partition需要确定两个位置，一个是pivot区间的开始位置，一个是pivot区间的结束位置
// 因此partition方法无法直接这是返回值，只能把partition写在quickSort方法中
public static void quickSort(int[] arr, int left, int right) {

    if (left >= right) {
        return;
    }

    // pivot的位置可以在开头，也可以在最后，也可以在随机位置
    // 标准写法是在开头或最后
    // pivot在开头的写法
    int pivot = arr[left];
    // 定义三个指针，左指针begin和右指针end，左指针在pivot后面，begin和i之间的距离就是pivot的数量
    int begin = left;
    int end = right;
    int i = begin + 1;

    while (i <= end) {
        if (arr[i] > pivot) {
            swap(arr, i, end);
            end--;
        } else if (arr[i] < pivot) {
            swap(arr, i, begin);
            i++;
            begin++;
        } else {
            i++;
        }
    }

    quickSort(arr, left, begin - 1);
    quickSort(arr, end + 1, right);
}

标准写法（非递归版本）

// 采用非递归的方法，首先要想到栈的使用，通过阅读递归调用部分的代码，思考如何用栈来代替。
// 递归调用的核心代码是 pivot = partition(a, low, high); 每次循环都必须包含这句核心代码，
// 可以想到，如果要对该行代码实现循环，只能对low和high采取操作，所以我们在栈中压入low和high，
// 每个循环弹出一对low和high，用于核心代码的实现，当栈空后就说明没有需要排序的部分了，结束循环。
private static void quickSort3(int[] arr, int left, int right) {

    if (left >= right) {
        return;
    }
    Stack<Integer> s = new Stack<>();
    s.push(left);
    s.push(right);

    // 类似于递归的操作
    while(!s.isEmpty()) {
        // 注意pop的顺序，先end再begin
        int end = s.pop();
        int begin = s.pop();
        int pivot = partition(arr, begin, end);
        // 若pivot在begin和end之间
        // begin和pivot之间的部分需要排序
        if (pivot > begin) {
            s.push(begin);
            s.push(pivot);
        }
        // pivot和end之间的部分需要排序
        if(pivot + 1 < end) {
            s.push(pivot + 1);
            s.push(end);
        }
    }
}

最坏情况的快排

对一个排好序的数组使用快排
quick_sort

分区Partition分析

每次分区都刚好分两半，这是最好的情况，时间复杂度是O(nlogn)
每次分区都分成1和n-1两个部分，这是最坏的情况，时间复杂度是O(n^2)
如果pivot将数组分为两部分，每部分的大小至少为n/10，则这是个好的pivot（经验值）。 假设每次分区都分成1:9两个部分，即(1/10):(9/10)，时间复杂度仍可以是O(nlogn)

但根据以上的推导过程可以看出，较大分区的占比越大，即log的底数越接近1，时间复杂度越高，因此针对这种情况，可以随机选取pivot的位置，然后不断重复分区，直到分区后的两个部分的大小都在(1/10)n和(9/10)n的区间

QuickSort(A[1..n], n)
    if (n == 1) then return;
    else
        // 随机选取pivot的位置，然后不断重复分区，直到分区后的两个部分的大小都在(1/10)n和(9/10)n的区间
        repeat
            pIndex = random(1, n)
            p = partition(A[1..n], n, pIndex)
        until p > (1/10)n and p < (9/10)n
        x = QuickSort(A[1..p–1], p–1) // p–1为A[1..p–1]的长度
        y = QuickSort(A[p+1..n], n–p) // n–p为A[p+1..n]的长度

选取到一个好的pivot的概率p是8/10，而选取到一个坏的pivot的概率(1 - p)是1/10（假设一个数组的长度是10，好的pivot只能是中间的8个位置中的一个）根据概率论Probability Theory可知，不断循环重复选择一个pivot直到这个pivot是好的预期次数：E[pivot choices] = 1/p = 10/8 < 2，这意味着上面的代码中从repeat到until这个代码块的执行次数是小于2次，由此可得，pivot分区除了1:9，2:8也是可行，因为E[pivot choices] = 1/p = 10/6 < 2

E[T(n)] = E[T(k)] + E[T(n – k)] + E[pivot choices] (n)
<= E[T(k)] + E[T(n – k)] + 2n
= O(nlogn)

再优化

先使用快速排序，经过多次递归后得到一个即将排序完成的数组，然后对整个数组执行插入排序（插入排序对即将排序完成的数组的排序速度非常快）

要点

随机选择pivot的得到的快排的时间复杂度是O(nlogn)
分区Partition的时间复杂度是O(n)
若不使用任何额外的空间，分区Partition的空间复杂度是O(1)，这就是快排不稳定的原因；若使用辅助数组，分区Partition的空间复杂度是O(n)，这可以让快排变成稳定
最坏情况有3种，升序，降序，所有的元素都相同。若题目规定要排的是升序，那原数组是降序的情况最坏 O(n^2)，因为还要做交换的操作；对于降序的题目，则原数组是升序的情况最坏 O(n^2)
递归版的平均空间复杂度是 O(logn)，最差空间复杂度是 O(n)，空间复杂度就是递归的深度，递归的时候使用的栈空间；非递归版也是在模拟出栈和入栈的过程，空间复杂度也是 O(logn)，最差空间复杂度也是 O(n)
既可以升序排序，也可以降序排序，例如把partition方法中的if中的 arr[begin] <= pivot 改为 arr[begin] >= pivot，arr[end] >= pivot 改为 arr[end] <= pivot，pivot > arr[end] 改为 pivot < arr[end] 即可