Leetcode No.75 颜色分类

一、题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] 示例 2：

输入：nums = [2,0,1] 输出：[0,1,2] 示例 3：

输入：nums = [0] 输出：[0] 示例 4：

输入：nums = [1] 输出：[1]

二、解题思路

对数组排序，要求常数空间，因此用快排。

快速排序是对冒泡排序的改进。其基本思想是基于分治法：在待排序nums[1...n]中任取一个元素privot作为基准，通过一趟排序将待排序表划分为独立的两部分nums[1...k-1]和nums[k+1...n],使得nums[1...k-1]中所有元素小于privot，nums[k+1...n]中所有元素大于或等于privot，则privot最终放在了其最终位置L(k)上，这个过程称作一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素为空为止，即所有元素放在了其最终位置上。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后将一个元素（基准元素）放到其最终的位置上。

首先假设划分算法已知，记为Partition()，返回的是上述中的K，注意到nums(k)已经在最终的位置，所以可以先对表进行划分，而对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序

三、代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        quickSort(nums,0,(int)nums.size()-1);
    }
    void quickSort(vector<int>& nums,int low,int high){
        if(low<high){
            int pivotpos=partition(nums,low,high);
            quickSort(nums,low,pivotpos-1);
            quickSort(nums,pivotpos+1,high);
        }
    }
    int partition(vector<int>& nums,int low,int high){
        int pivot=nums[low];
        while(low<high){
            while(low<high&&nums[high]>=pivot){
                high--;
            }
            nums[low]=nums[high];
            while(low<high&&nums[low]<=pivot){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=pivot;
        return low;
    }
};

四、复杂度分析

空间复杂度：

由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。

最好情况下为log2(n+1)

最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n);

平均情况下，栈的深度为O(log_{2}n).

因而空间复杂度在最坏情况下为O(n)，平均情况下为O(log_{2}n)

复杂度：

快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。快速排序的最坏情况发生在两个区域分别n-1个元素和0个元素时，这种最大程序的不对称性若发生在每一层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度o(n^2)。