关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年4月1日
排序算法(3) — O(n log(n)) — 快速排序/归并排序

写在前面

这次是两种大家十分熟悉也是常见的东西,在中间的代码力玩花样的题并非没有,总而言之这是两种十分神奇的算法了qwq

归并排序

时间复杂度: O(n log(n))
空间复杂度: O(n)

突然间想起几篇前的O(n^2)….真是感人
然后再看看前面的代码长度,在看看下面的…
也是很感人呢2333

我还不如等量子计算机出来直接冒泡

#include <cstdio>
using namespace std;

int n;
int result[110000];
int a[110000];

void marge(int *data,int start,int end,int *result){// 合并区间
    int left_start,result_start,right_start;
    left_start=result_start=start;
    right_start=(start+end+1)/2+1;

    while(left_start<=(start+end+1)/2&&right_start<=end){
        if(data[left_start]<data[right_start]) result[result_start++]=data[left_start++];
        else result[result_start++]=data[right_start++];
    }

    while(left_start<=(start+end+1)/2) result[result_start++]=data[left_start++];
    while(right_start<=end) result[result_start++]=data[right_start++];
} 

void margesort(int *data,int start,int end,int *result){// 二分
    if(end-start==1){// 刚好差为1,那么这两个相邻,就可以排序
        if(data[start]>data[end]){
            int temp=data[end];
            data[end]=data[start];
            data[start]=temp;
        }   
        return ;
    }
    else if(end-start==0) return ;//相同你排个瓜皮啊
    else {
        margesort(data,start,(start+end+1)/2,result);//继续二分排序
        margesort(data,(start+end+1)/2+1,end,result);

        marge(data,start,end,result);// 合并

        for(int i=start;i<=end;i++) data[i]=result[i];//排序完的总的回去吧233
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    margesort(a,1,n,result);

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

我给你讲这个代码还是压过行的

上面的注释我觉得知道原理估计看不懂,说一下归并排序的原理:

  1. 将一个长度为n的数列分成2/n的数列<分>
  2. 分到只剩两个的时候排序<治>
  3. 将每个区间进行合并<和>

所以这是一个分治算法,“分而治之”,“分完要和”。

建议思考两个问题 并不会公布答案,因为不自己想的话根本理解不了 如果你是dalao建议你左上角,这是一篇对你没有用的文章:

  • 在二分排序的时候(start+end+1)/2(start+end+1)/2+1是为了什么,可不可以替换?
  • 中间几个<=是否可以换成<

快速排序

理论最优速度: O(n log(n))
最差速度: O(n^2)
空间复杂度: O(n log(n))

我们找出一个“哨兵”,然后找出比他大的和比他小的,然后分成两列<分>,知道最后只剩两个完成排序<治>,然后回溯输出<合>

又是一个分治算法

代码:

#include <cstdio>
using namespace std;

int n;
int a[110000];

void qsort(int *data,int s,int e){
    int o_l=s,o_r=e;
    int base=data[(s+e)/2];//取中快排
    do{
        while(data[s]<base) s++;// 比自己大的
        while(data[e]>base) e--;//比自己小的
        if(s<=e){//上面两个循环都被打断说明顺序不对,交换一下
            int temp=data[s];
            data[s]=data[e];
            data[e]=temp;
            s++;
            e--;
        }
    }while(s<=e);
    if(o_l<e) qsort(data,o_l,e);//确保不越界
    if(s<o_r) qsort(data,s,o_r);

}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    qsort(a,1,n);

    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

End

这两种算法是比较常见的排序算法,原理都是分治,不过归并相对稳定一些,不容易翻车


textsms