'简单排序'

2020-05-31

归并排序

一种简单却十分高效的排序方法，非常适合新手学习

引言

在C语言的教材中，介绍了冒泡排序和选择排序等几种简单的排序。操作简单，容易理解，但是时间复杂度却比较高。今天在这里介绍另一种简单排序 -归并排序，听起来就有B格。

优点

归并排序的优点简单来讲就是稳稳的快。

首先归并排序的时间复杂度是nlog(n)，比起n^2的冒泡排序快乐不少

其次它稳定，快排的时间复杂度也是nlog(n), 但是当数组完全逆序的情况下，快排的时间复杂度就会和冒泡排序一样变成n^2了，然而归并排序则是稳稳的nlog(n)，而且我个人觉得归并排序好理解一点。

原理

归并排序的原理就是二分法，分而治之。大化小，小化了。

代码

#include<iostream>

#define rep(i, a, n) for(int i = a; i < n; i++)
#define res(i, a, n) for(int i = a - 1; i >= n; i--)
using namespace std;
const int N = 10020;

template<class T>       //这个是模板， 很强大的东西
void MergeSort(T *l, T *m, T *r){
    T *x = l, *y = m;
    int len = r - l;
    T *a = new T[len + 5], index = 0;
/**************************************************/
/**/while(x < m && y < r){                      /**/
/**/if(*x < *y)     a[index++] = *(x++);        /**/
/**/    else            a[index++] = *(y++);    /**/
/**/}                                           /**/
/**/                                            /**/
/**/while(x < m)        a[index++] = *(x++);    /**/
/**/while(y < r)        a[index++] = *(y++);    /**/
/**************************************************/
    /*以上这段代码的思路， 说的简单的就是， 一次遍历排好序*/
    /*比如说当传进来的数组为{2， 3， 1， 4}的时候就会排成{1， 2， 3， 4}*/
    /*因为1 < 2， 所以先放1， 然后2 < 4， 再放2， 3 < 4， 放3， 然后退出第一个循环， 在第三个循环里面放4， 然后就排好了*/
    /*但是， 如果数组是{3， 2， 4， 1}的时候就会排成{3， 2， 4， 1}， 没有变化， 就不会得到我们想要的功能*/
    /*然而并不会出现这种情况， 因为我们会先把{3， 2}排成{2， 3}， {4， 1}排成{1， 4}*/
    /*这就是分治的nb之处了*/

    rep(i, 0, index)    l[i] = a[i];
    /*然后把原数组局部覆盖就好了*/
}

template<class T>
void sort(T *l, T *r){//首先取名字一定要有B格， 我不加algorithm头文件， 但我依旧可以用sort， 而且还是绿色， 这就很有B格
    T *m = l + (r - l) / 2;
    if(r - l > 1){
        sort(l, m);     //每次都分成两部分， 大化小
        sort(m, r);     //当r - l <= 1 的时候， 即足够小的时候， 就不分了， 小化了
    }
    MergeSort(l, m, r); //sort体现的是分治的思想， MergeSort则是操作
}

int main(){
    int n;
    char a[N];
    while(cin >> n){
        rep(i, 0, n)    cin >> a[i];
        sort(a, a + n);
        rep(i, 0, n)    cout << a[i] << " ";      cout << endl;
    }
    return 0;
}

/*
10
1 6 2 7 5 3 1 2 4 1

10
1627531241

8
德玛西亚

*/

/*
给了几组数据， 第三组理所当然会出现问题
*/