再说快速排序

柔情只为你懂 2023-06-04 04:58 11阅读 0赞

快速排序作为排序算法中的战斗机，一直是排序算法里面用的最多也是考的最多的一个算法

已经证明，对n个元素进行排序，最优的算法也是需要NLogN的时间复杂度，而快速排序的时间复杂度就是NlogN，

所以快速排序是排序算法中最优算法中的一个，下面我们继续来探索一下神奇的快速排序算法吧

**快速排序的核心思想：每次排序把每一个元素k移动到正确的位置，并且把小于k的元素都移动到k的左边，大于k的元素都移动到k的右边**

**待排序的数列x\[\]，长度为n**

**算法一：初始化k=x\[m\](m为待排序的第一个元素)，对于每一个元素x\[i\](i>m)，如果x\[i\]>=k，i++;如果x\[i\]<k,swap(x\[i\],x\[++m\])**

**代码如下：**

void qsort1(int l,int h)
    {
        if(l>=h) return; 
        int m=l;
        for(int i=l;i<=h;i++)
        {
            if(x[i]<x[l])
            {
                int temp=x[i];x[i]=x[++m];x[m]=x[i];
            }
        }
        int temp=x[l];x[l]=x[m];x[m]=x[l];
        qsort1(l,m-1);
        qsort1(m+1,h);
    }

** 算法一对随机整数组很有效，但是对于n个相同元素的时候，其性能会急剧下降，因为每次都要花O(n)的时间来去掉一个元素，总共需要接近O(n2)的时间复杂度**

**于是诞生了双向靠拢的算法二，**

void qsort2(int l,int h)
    {
        if(l>=h) return; 
        int t=x[l],i=l,j=h;
        while(i<j)
        {
            while(i<j&&x[j]>t) j--;
            x[i]=x[j];
            while(i<j&&x[i]<t) i++;
            x[j]=x[i];
        }
        x[i]=t;
        qsort2(l,i-1);
        qsort2(i+1,h);
    }

**算法二比算法一优化的地方是对于相同的元素，每次都可以把当前元素的位置定位在接近中间的位置，这使得总时间接近于O(NlogN)的时间复杂度**

改进后的算法二虽然提高了对相等数列的效率，但对于已经排序好的升序来说，还是接近O(N2)的时间复杂度，原因是我们每次都是以第一个元素为划分

**改进的算法三想法如下：swap(l,randint(l,h))    ,randint(l,h)保证产生一个\[l,h\]范围的整数即可**

int randint(int l,int h)
    {
      srand(unsigned(time(NULL)));
      int temp=rand()%(u+1);
      return temp>l?temp:h-temp;
    }

这样之后，快速排序还有哪里可以改进呢？

**我们可以发现快速排序话费大量的时间来排序很小的子数组，如果用插入排序之类的简单算法来排序这些很小的子数据，程序的子速度会更快  **

if(h-l<cutoff)
        return

如何确定cutoff的值是一个难点，这个可以通过实验来得出，比如把n固定为100000，然后对cutoff在\[1,100\]内的每个可能取值都运行一遍，比较运行时间

最后的算法四代码如下：

int randint(int l, int h)
    {
      srand(unsigned(time(NULL)));
      int t = rand()%(h-l+1);
      return l+t;
    }
    void qsort4(int l,int h,int cutoff)
    {
        if(l-h<cutoff) return;
        int r=randint(l,h);
        int t=x[r];x[r]=x[l];x[l]=t;
        t=x[l];
        int i=l,j=h;
        while(i<j)
        {
            while(i<j&&x[j]>t) j--;
            x[i]=x[j];
            while(i<j&&x[i]<t) i++;
            x[j]=x[i];
        }
        x[i]=t;
        qsort4(l,i-1);
        qsort4(i+1,h);
    }
    void isort(int h)
    {  
      for (int i = 0; i < h; ++i)
      {
        int temp=x[i];int j;
        for(j=i;j>0&&x[j-1]>temp;j--)
        {
          x[j]=x[j-1];count++;
        }
        x[j]=temp;
      }
    }
    qsort4(l,h,cutoff);
    isort(h);

最后再来看一个利用快速排序思想的问题：

**如何在O(n)的时间里找到第k小的元素？**

代码如下

#include "stdlib.h"
    #include "time.h"
    #include <iostream>
    #include <iomanip>
    using namespace std;
    int x[100]={
        0};
    int randint(int l, int h)
    {
        srand(unsigned(time(NULL)));
        int t = rand()%(h-l+1);
        return l+t;
    }
    void search_kth(int l,int h,int k)
    {
        if(l>=h) return;
        int r = randint(l,h);
        int t = x[r];x[r]=x[l];x[l]=t;t=x[l];
        int i=l,j=h;
        while(i<j)
        {
            while(i<j&&x[j]>=t) j--;
            x[i]=x[j];
            while(i<j&&x[i]<=t) i++;
            x[j]=x[i];
        }
        x[i]=t;
        if(i<k) search_kth(i+1,h,k);
        else if(i>k) search_kth(l,i-1,k);
    }
    int main(int argc, char const *argv[])
    {
        srand(unsigned(time(NULL)));
        for (int i = 0; i < 100; ++i)
        {
            x[i]=rand()%100;
            cout<<setw(2)<<x[i]<<" ";
        }
        cout<<endl;
        search_kth(0,99,50);
        cout<<endl;
        for (int i = 0; i < 100; ++i)
        {
            cout<<setw(2)<<x[i]<<" ";
        }
        return 0;
    }

转载于:https://www.cnblogs.com/qwj-sysu/p/4040442.html