本文的图都来自《算法图解》
分治 D&C —— divide and conquer
基线条件 —— 最简单的情况
递归过程为判断基线条件,每次递归向基线条件靠拢。
编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素。陷入困境时,请检查基线条件是不是这样的。
快排是一种分治算法
需要对下列数组进行排序
选择一个数作为pivot,这里选了3,把<=
pivot的数排在pivot左
把>
pivot的数排在pivot右,接下来对左右两部分递归调用函数进行快排。。。整个数组就排好了。
我们也可以选择5作为pivot如下
我们取每个数组的第一个元素作为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; } };