本文的图都来自《算法图解》

分治

分治 D&C —— divide and conquer

基线条件 —— 最简单的情况
递归过程为判断基线条件，每次递归向基线条件靠拢。

编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

快排 quick sort

快排是一种分治算法

快排思想

需要对下列数组进行排序

选择一个数作为pivot，这里选了3，把<=pivot的数排在pivot左
把>pivot的数排在pivot右，接下来对左右两部分递归调用函数进行快排。。。整个数组就排好了。

我们也可以选择5作为pivot如下

qsort简单实现

我们取每个数组的第一个元素作为pivot

from typing import List

def qsort(array: List[int]) ->List[int]:
    if len(array)<2: return array
    pivot = array[0]
    less = [x for x in array[1:] if x<=pivot] #从array[1:]防止和pivot重复
    greater = [x for x in array[1:] if x>pivot ]
    return qsort(less) +[pivot] + qsort(greater)
    

上面的代码用到了python的typing模块，用来类型检查,详见python模块分析之typing

时间复杂度——最好情况和最差情况

最差情况递归n次，递归栈高度 O ( n ) O(n) O(n)

最好情况 每次恰好平衡 递归栈高度 O ( log ⁡ n ) O(\log{n}) O(logn)

而无论最好情况还是最差情况 每层需要时间都为 O ( n ) O(n) O(n)

快排时间复杂度最好情况 O ( n log ⁡ n ) O(n\log{n}) O(nlogn)，最差 O ( n 2 ) O(n^2) O(n2)。最佳情况也是平均情况，每次随机选择一个pivot，时间复杂度则为 O ( n log ⁡ n ) O(n\log{n}) O(nlogn)

随机快排

leetCode排序数组
实际代码不可能像简单实现那样进行大量拷贝，用swap操作代替拷贝

C++版本代码

class Solution {
    int partition(vector<int>& nums, int low, int high) {
        int i = rand()%(high-low+1)+low;//随机选择pivot
        swap(nums[i],nums[low]);//pivot跟第一个元素交换
        int pivot = nums[low];
         i = low;
        for (int j = low+1; j <= high; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i], nums[low]);// left~i 比 pivot 小于等于 i+1d
        return i;//返回的是pivot新位置
    }
    void quickSort(vector<int>& nums, int low, int high){
        //low>=high 数组只有一个元素时原样返回
        if(low<high){
        int pos = partition(nums,low,high);
        quickSort(nums,low,pos-1);
        quickSort(nums,pos+1,high);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
};