• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

快速排序

开发技术 开发技术 2周前 (05-01) 6次浏览

快速排序算法

  快速排序算法思想就是每一次选取一个元素,然后以此元素为基准,将大于基准的元素放到基准的后面,将小于基准的元素放到基准的前面,然后递归下去直到只有他自己为止。平均算法时间复杂性为O(nlogn)。由于有时候会遇到数组的大部分是符合降序排序的,这样就会大大影响时间复杂性。因此,再程序中采取一个随机数来作为基准。

程序实现

#include<iostream>
#include<set>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<sstream>

using namespace std;


//进行分割排序,并且返回排序后基准的位置
template <typename  Type>
int Partition(Type a[],int p,int r){
    int i=p,j=r+1;  //这里的j=r+1,之所以奖赏一是因为后面的--j,要先做减法,为了防止最后一个元素称为漏网之鱼
    Type x=a[p];    //这里将数组的起始点下标p指向的元素作为基准
    //将小于x的元素交换到左边区域,将大于x的元素交换到右边区域
    while(true){
        while(a[++i]<x&&i<r);   //先扫描左边的,直到找到比x大的元素停下来
        while(a[--j]>x);        //找到右边比x小的元素停下来
        if(i>=j)break;          //结束条件
        Swap(a[i],a[j])         //将他俩进行交换
    }
    //这里j指向的要小于等于x
    a[p]=a[j];
    a[j]=x;
    return j;
}

//进行随机分割,避免数组整体倒序造成时间复杂度升高
template <typename  Type>
int RandomizedPartition(Type a[],int p,int r){
    int i=random(p, r);
    swap(a[i],a[p]);
    return Partition(a,p,r);
}

/*
快速排序算法
参数:
    a[]:数组;
    p  :数组起点
    r  :数组终点
*/
template <typename  Type>
void Quicksort(Type a[],int p,int r){
    if(p<r){
        int q=RandomizedPartition(a,p,r);
        Quicksort(a,p,q-1);
        Quicksort(a,q+1,r);
    }
}


程序员灯塔
转载请注明原文链接:快速排序
喜欢 (0)