荷兰国旗问题

问题一

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

思路

逐次遍历数组，涉及五个概念：当前index、当前值curValue、虚拟的“小于区”、虚拟的“大于区”，逐次遍历过程中会有三种情况：

• curValue < num，则“小于区”右扩一个，且最后一个值与curValue交换，index++
• curValue > num，则“大于区”左扩一个，且区的第一个值与curValue交换，index不变

问题二（荷兰国旗问题）

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

思路

逐次遍历数组，涉及五个概念：当前index、当前值curValue、虚拟的“小于区”、虚拟的“中间区”、虚拟的“大于区”，逐次遍历过程中会有三种情况：

• curValue < num，则当前值与小于区下一个值交换，小于区右扩一个，i++
• curValue == num，则直接index++
• curValue > num，则当前值与大于区前一个交换，大于区左扩一个，i不动

快速排序

快速排序的思路跟上述荷兰国旗问题的思路类似，都是通过分区来解决。

举个🌰（快排1.0版本）：

假设现在需要对数组[4,3,5,6,5,0,1,7,8,5]进行快速排序，那么步骤如下：

• step1（第一次分区）：以数组最后一个数5作为基准，再将数组所有的数（包括最后一个数5）进行分区，得到[4,3,0,1,5,5,5,8,7,6]。这里的“中间区”[5,5,5]就产生了，并且它们的位置是确定的，之后的比较就不需要再比较“中间区”了，一次遍历就确定了一大块数据，所以叫快速排序。
• step2（第二次分区）:对”小于区“[4,3,0,1]进行分区，以最后一个值1作为基准，就得到[1,0,3,4]；对“大于区”[8,7,6]进行分区，以6作为基准就得到[6,7,8]。
• 以此进行递归，就会得到最后排好序的数组

快排1.0版本的时间复杂度

从分析过程可以看出，每次分区都只是确定了一个数的位置。那么其时间复杂度是多少呢？

举个🌰：假如对数组[1,2,3,5,6,7,8,9]进行快速排序（期间没有“小于区”和“中间区”）。当以9为基准的时候，遍历整个数组，最终确定了9的位置；当以8为基准的时候，遍历[1,2,3,5,6,7,8]，才确定了8的位；...，总的时间复杂度就是9+8+7+...。当数组特别大时，时间复杂度就是O(N2)O(N^2)O(N2)

时间复杂度高的原因

先来说一种情况，如果我们找的基准，刚好使得“小于区”和“大于区”数据量一样大，这就使得递归过程符合Master公式（什么是Master公式？看这里）:T(N)=2∗T(N/2)+O(N)T(N)=2*T(N/2)+O(N)T(N)=2∗T(N/2)+O(N)，那么时间复杂度就是O(N∗logN)O(N * {logN})O(N∗logN)。

所以，快排1.0版本的时间复杂度之所以高，是因为基准找的不对（最好情况时间复杂度是O(N∗logN)O(N * {logN})O(N∗logN)，最坏情况时间复杂度是O(N2)O(N^2)O(N2)）。因此我们需要对上述的快排算法进行优化。

快排2.0版本

在快排1.0的版本基础上，对于基准的选取做了优化：在数组中随机选择一个数，并与最后一个数进行交换，用这个随机选取的数作为基准。

public static void quickSort(int[] arr, int l,int r){
    if(l<r){
        swap(arr, l+(int)(Math.random() * (R-L+1)), r);
        int[] p = partition(arr,l,r);
        quickSort(arr,l,p[0]-1);  // 小于区
        quickSort(arr,p[1]+1,r);  // 大于区
    }
}
// 这是一个处理arr[l...r]的函数
// 返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[0] res[1]
// 假设[3,6,2,5,7,5],随机数选到了5并和最后一个数交换，然后得到[3,2,5,5,6,7]，那么函数返回等于区域的左右边界，也就是第一个5的index值和最后一个5的index值：{2，3}
public static int[] partition(int[] arr,int l, int r){
    int less = l-1;
    int more = r;
    while(l<more){
        if(arr[l]<arr[r]){
            swap(arr,++less, l++);
        }else if(arr[l]>arr[r]){
            swap(arr, --more, l);
        }else{
            l++;
        }
    }
    swap(arr, more, r);
    return new int[] {less+1, more}
}
复制代码

为什么快速排序要随机化

由于基准值是随机的，因此最后的时间复杂度都是概率性问题，而如果去把这些结果值求取期望值，其时间复杂度就是O(N∗logN)O(N * {logN})O(N∗logN)。

在上述我们已经知道最好的情况的Master公式是T(N)=2∗T(N/2)+O(N)T(N)=2*T(N/2)+O(N)T(N)=2∗T(N/2)+O(N)，也就是说（假设数组长度为5），以下情况等概率：

T(N)=T(N)+O(N)T(N)=T(N)+O(N)T(N)=T(N)+O(N)    // 全部都是小于区

T(N)=T(N/5)+T(4/5∗N)+O(N)T(N)=T(N/5)+T(4/5*N)+O(N)T(N)=T(N/5)+T(4/5∗N)+O(N)  // 小于区:大于区=1:4

T(N)=T(2/5∗N)+T(3/5∗N)+O(N)T(N)=T(2/5*N)+T(3/5*N)+O(N)T(N)=T(2/5∗N)+T(3/5∗N)+O(N)   // 小于区:大于区=2:3

T(N)=T(3/5∗N)+T(2/5∗N)+O(N)T(N)=T(3/5*N)+T(2/5*N)+O(N)T(N)=T(3/5∗N)+T(2/5∗N)+O(N)   // 小于区:大于区=3:2

T(N)=T(4/5∗N)+T(1/5∗N)+O(N)T(N)=T(4/5*N)+T(1/5*N)+O(N)T(N)=T(4/5∗N)+T(1/5∗N)+O(N)  // 小于区:大于区=4:1

T(N)=T(N)+O(N)T(N)=T(N)+O(N)T(N)=T(N)+O(N)    // 全部都是大于区

通过一大堆数学公式，求得的时间复杂度期望值是O(N∗logN)O(N * {logN})O(N∗logN)。

快速排序的空间复杂度与时间复杂度

想要知道空间复杂度就需要了解以下两点：

• 快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间。
• 每次递归需要的空间是固定的，总体空间复杂度即为递归层数。
• 时间复杂度与空间复杂度都是求概率累加。

最好/平均情况

最好的情况是每次递归都平分数组，一共需要递归logN次，每次需要N时间。  分析如下：

我们假设一共有N个数需要排序，也就是二叉树一共有N个结点。如果把二叉树的图画出来，每次partition（分区）相当于处理所有当前区间的结点。

• 第一层partition处理了N个点。
• 第二层调用partition两次，每次处理N/2个点，总体还是N个点。
• 第三层调用了partition四次，每次处理N/4个点，总体还是N个点。

所以时间复杂度 = 二叉树的层数(logNlogNlogN) * 每层处理的结点个数 (N)

总结：最好/平均情况下，空间复杂度是O(logN)O({logN})O(logN)，时间复杂度是O(N∗logN)O(N * {logN})O(N∗logN)

最差情况

在最差的情况下，每次都把数组分成1和N-1，一共需要递归N次，每次需要N时间，每次只完成了一个元素，那么空间复杂度为O(N)O(N)O(N)

总结：最差情况下，空间复杂度是O(N)O(N)O(N)，时间复杂度是O(N2)O(N^2)O(N2)

Leetcode-912. 排序数组

var quickSort = function(arr, start, end){
    if(start<end){
        // 1.找出一个随机数作为基准值，并与最后一个值交换
        swap(arr,start+ Math.floor(Math.random()*(end-start+1)), end);
        // 2.找出中间区域的左右边界index值
        const p = partition(arr, start, end);
        // 3.递归排序小于区和大于区
        quickSort(arr, start, p[0]-1);
        quickSort(arr, p[1]+1, end);
    }
}
var swap = function(arr, i1, i2){
    let temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
}
var partition = function(arr, l, r){
    // 分为三种情况：
    // 1.curValue<pivot,则当前值与小于区下一个值交换，小于区右扩一个，i++
    // 2.curValue==pivot，则i++
    // 3.curValue>pivot，则当前值与大于区前一个交换，大于区左扩一个，i不动
    let less = l-1; // 定义小于区的范围为 （负无穷大，less]
    let more = r; // 定义大于区的范围为 [r+1, 正无穷大）
    while(l < more){
        if(arr[l] < arr[r]){
            swap(arr, l++, ++less);
        }else if(arr[l]>arr[r]){
            swap(arr, l, --more);
        }else{
            l++;
        }
    }
    // 此时已经划分为四个区域了：小于区、等于区[无数个pivot]、大于区、一个pivot
    // 然后需要将大于区的一个数与最后一个pivot交换，那么就会被分为三个区域：小于区、等于区、大于区
    swap(arr, more, r);
    return [less+1, more]
}
var sortArray = function(nums) {
    quickSort(nums, 0, nums.length - 1); 
    return nums
};
复制代码

相关链接：

七天刷爆LeetCode，顶级算法大神