快速排序算法sort分析

川长思鸟来 2022-08-06 07:16 99阅读 0赞

快速排序的思想是分治法的思想。

一般是按照这个序列的首元素为 mid 基准，把比比mid大的元素放在后面。比 mid 小的元素放前面。然后依次递归，把在 mid 前面的所有元素当成一个新的序列进行刚才的操作，在mid后面的元素看成一个新的序列也进行这样的操作，直到这样得到的序列为一个元素。则排序完成。

当然为基准的元素不一定非要是1：首元素，也可以选2：末尾元素，或者3中间位置元素，4取首、末、中的中间值，4、取一个随机数。当然这个基准选取的好的话算法的效率会不同，最好是每次取一个所有元素排序之后的中间元素，这样算法的效率最高。

加入我们以序列 49,38,65,97,76,13,27 为例，取首元素为基准。

经过第一次划分得到【27,38,13】 49 【76 97 65】

然后前面序列为27为基准【13】27 【38】 后面元素以76为基准 得到【65】 76 【97】

这样元素就有序了。

可见，算法其实很简单，分治法策略这些可以用一个递归函数来实现，

void Qsort(int low,int high)
    {
        int mid;
        if(low<high)
        {
            mid = Partition(low,high);
            Qsort(low,mid-1);
            Qsort(mid+1,high);
        }
    }

接下来是按照基准划分了。这样来实现

int Partition(int low,int high)
    {
        int i = low,j = high,pivot = num[low];
        while(i<j)
        {
            while(i<j && num[j]>=pivot)
                j--;
            if(i<j)
                swap(num[i++],num[j]);
            while(i<j && num[i]<=pivot)
                i++;
            if(i<j)
                swap(num[i],num[j--]);
        }
        return j;
    }

这样就实现了快速排序

#include <iostream>
    #include <cstdio>
    using namespace std;
    int num[500];
    int Partition(int low,int high)
    {
        int i = low,j = high,pivot = num[low];
        while(i<j)
        {
            while(i<j && num[j]>=pivot)
                j--;
            if(i<j)
                swap(num[i++],num[j]);
            while(i<j && num[i]<=pivot)
                i++;
            if(i<j)
                swap(num[i],num[j--]);
        }
        return j;
    }
    void Qsort(int low,int high)
    {
        int mid;
        if(low<high)
        {
            mid = Partition(low,high);
            Qsort(low,mid-1);
            Qsort(mid+1,high);
        }
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&num[i]);
            Qsort(0,n-1);
            for(int i=0;i<n;i++)
                printf("%d%c",num[i],i==(n-1)?'\n':' ');
        }
        return 0;
    }