手动实现快排

曾经终败给现在 2022-02-04 12:43 239阅读 0赞

**ps：基于比较的排序算法最快就是nlgn的时间复杂度**  
快排的主要思想就是找到一个key值 比他大的放右边 比他小的放在左边  
然后对该key值左边和右边同时进行该操作，即为递归，直到排好序

surprise，只要是不是已排序好的最差情况，其余情况该算法的时间复杂度均趋向于nlogn  
很神奇 想证明的话可以用极限和树的思想计算出时间复杂度，就会发现除最差情况其余情况都是nlogn的常数倍的时间复杂度  
PS:更新说明，C++内部实现sort找的k值为(l+r)/2; 这是由于随机化函数的时间复杂度很高的原因，但是也可以证明你无法找到一个数组使这种找k值的方式的时间复杂度达到n^2

#include<bits/stdc++.h>
        using namespace std;
        const int N=2e5+7;
        int a[N];
        void sdkp(int l,int r)///l为首下标，r为末下标
        {
            if(r<l)
                return;
            int k=a[l];
            int i,j;
            i=l;j=l+1;
            for(;j<=r;j++)
            {
                if(a[j]<k)
                    swap(a[j],a[i+1]),i++;
            }
            swap(a[i],a[l]);
            sdkp(l,i-1);sdkp(i+1,r);
        }
        int main()
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
    
        }
        sdkp(0,n-1);
        for(int i=0;i<n;i++)
            cout<<a[i]<<' ';
        cout<<endl;
    }

第一波填坑 优化点在于随机数选取key值从而避免最差情况，  
在长期实践过程中，随机化快排比归并排序快三倍以上，但是归并排序保证即使是最坏情况下，仍然只有nlgn的时间，随机化选取key值理论上是有可能还是会出现最坏情况，但这也许和太阳从西边出来的概率一样，但归并还要占用栈呢  
证明中出现了一个积分问题（ps：计算机中的lg都指的是log2），我求解出了前半部分，后面的不会整理了，有兴趣的话随便解下，谢谢留言  
（k=2,3,…n-1) klgk的和小于等于 1/2n^2lgn-1/8lgn

///最基本的实现主要是这个想法，埋坑，以后会有其他实现的