苏州高端网站,手机微信怎么建立公众号,湖北网站seo策划,网站建设运转文章目录 #x1f680;前言#x1f680;快排的核心过程partition#xff08;划分过程#xff09;#x1f680;快排1.0#x1f680;随机快速排序#x1f680;稳定性 #x1f680;前言
铁子们好啊#xff01;继续我们排序算法今天要讲的是快排#xff0c;通常大家所说… 文章目录 前言快排的核心过程partition划分过程快排1.0随机快速排序稳定性 前言
铁子们好啊继续我们排序算法今天要讲的是快排通常大家所说的快排都是指随机快速排序这里阿辉会详细的讲快排及其优化以及复杂度和稳定性的分析话不多说开始我们今天的学习吧
快排的核心过程partition划分过程
在整个快排的过程中快排最为核心的过程就是划分过程 划分过程就是给定一个数作为划分值将待划分的数组分成小于划分值的部分放在数组左边、等于划分值的部分在中间和大于划分值的部分在右边为了方便下文阿辉就直接简称为小于区、等于区和大于区 对于划分过程是怎么样的思路呢 对于一个数组的划分我们需要三个指针来控制整个划分过程 用指针i来控制整个数组的遍历用指针left来管理小于区域用指针right来管理大于区域 假设我们取3作为划分值i从左向右遍历数组要分三种情况
当i指向的元素小于划分值时i指向的数要与left指向的数字交换然后i同时left当i指向的元素大于划分值时i指向的数要与right指向的数字交换然后--righti不变当i指向的元素等于划分值时仅有i自增
为什么这么设计呢 left控制着小于区在left左边的元素都属于小于区right控制着大于区在right的右边的元素都属于大于区而等于区的左边界是left右边界是rightleft和right自身以及他们俩之间的元素都属于等于区。 left代表小于划分值的元素发货到小于区--right代表大于划分值的元素发货到大于区。为什么发货到小于区i因为i是从左向右遍历的left的数换到i位置不需要再看一遍了而发货到大于区的时候right的数换到i位置还没有看过还得再看一遍它该发货到哪个区域。 对于上面的数组划分完是下面这样的 让数组这样划分成这样后对于中间的等于区域就不需要在管了因为就算排好序它也应该在这个位置前面都是小于它的后面都是大于大于它的你说它是不是该在这 附上partition函数的代码
void partition(int a[],int l,int r,int x){//划分函数//l是待划分区域左边界r是待划分过程右边界x是划分值int i l;//遍历偏移量while(i end){//iend时说明要划分的区域已经划分完成if(a[i] x){//遇到等于区域数不用管i直接遍历下一位置i;}else if(a[i] x){//遇到小于区域数发货到小于区域swap(a[i],a[l]);//l、i同时去到下一个位置}else{//遇到大于区域数发货到大于区域swap(a[i],a[r--]);//r同时去到下一位置}}}划分过程是O(N)的时间复杂度因为划分过程会遍历数组整个元素跳出循环的条件是ir在每一次循环过程中都是i或者--r所以时间复杂度是O(N)
快排1.0
有了上面的划分过程就好办了请出我们的老伙计——递归当我们对于原数组等于区排好了我们给原数组小于区域和大于区再次划分然后递归下去递归到数组只有1个元素时数组天然有序作为我们的base case也就是递归的限制条件。 现在我们的重心就是要选定划分值但是对于固定流程的程序我们一定可以找到让这个程序最难受的数据状况比如数组中只有1~9这9个元素如果我们划分值选在数组最右的元素对于下面这个数组 我们每次都会选到数组最大的元素导致没有大于区域而且一次递归只能排好一个位置的数对于划分过程partition函数的时间复杂度是O(N)然后每次待排序数组递减明显和冒泡、插入一个级别的O(N2)的时间复杂度也就是说快排1.0的时间复杂度是O(N2) 代码 int begin,end;void quicksort(int a[],int l,int r){//快排主逻辑if(l r) return;//base case终止条件int x a[r];//以数组最右元素作为划分值partition(a,l,r,x);//给数组根据随机出的划分值做划分//用临时变量捕捉当前的边界全局变量会被子递归过程更改int left begin;int right end;quicksort(a,l,left - 1);//左部分递归quicksort(a,right 1,r);//右部分递归}void partition(int a[],int l,int r,int x){//划分函数//l是划分区域左边界r是划分过程右边界begin l;//全局变量记录等于区域左边界end r;//全局变量记录等于区域右边界int i l;//遍历偏移量while(i end){//iend时说明要划分的区域已经划分完成if(a[i] x){//遇到等于区域数不用管i直接遍历下一位置i;}else if(a[i] x){//遇到小于区域数发货到小于区域swap(a[i],a[begin]);//begin、i同时去到下一个位置}else{//遇到大于区域数发货到大于区域swap(a[i],a[end--]);//end、i同时去到下一位置}}}我们想要的是O(NlogN)的快排可不是这个和三大最挫排序一样效率的排序好让我们见识一下全盛时期的快排吧
随机快速排序
其实随机快排就比上面的快排1.0只换了一行代码就让快拍的时间复杂度达到了O(NlogN) 代码 int begin,end;void quicksort(vectorint a,int l,int r){//快排主逻辑if(l r) return;//base case终止条件int x a[l rand() % (r - l 1)];//随机一个划分值partition(a,l,r,x);//给数组根据随机出的划分值做划分//用临时变量捕捉当前的边界全局变量会被子递归过程更改int left begin;int right end;quicksort(a,l,left - 1);//左部分递归quicksort(a,right 1,r);//右部分递归}void partition(vectorint a,int l,int r,int x){//划分函数//l是划分区域左边界r是划分过程右边界begin l;//全局变量记录等于区域左边界end r;//全局变量记录等于区域右边界int i l;//遍历偏移量while(i end){//iend时说明要划分的区域已经划分完成if(a[i] x){//遇到等于区域数不用管i直接遍历下一位置i;}else if(a[i] x){//遇到小于区域数发货到小于区域swap(a[i],a[begin]);//begin、i同时去到下一个位置}else{//遇到大于区域数发货到大于区域swap(a[i],a[end--]);//end、i同时去到下一位置}}}就改了对与划分值的选取用了随机的方式在数组中随机选取一个元素作为划分值随机快速排序的时间复杂度是O(NlogN)这里是为什么呢阿辉也只是记住并不知道原理这是数学家把每一种结果的概率都求出来然后算出期望随机快排的时间复杂度收敛于O(NlogN)在算法导论上有证明感兴趣的小伙伴可以去研究
稳定性
随机快排是没有稳定性的换句话说是划分过程没有稳定性比如 对于这样的数组i位置与right一换最后位置的2一下子跨越他前面那么多2所以快排没有稳定性但是快排比归并以及堆排序都快是常数时间上快
