思路

计划以10W，50W样例来对两组算法进行测试。根据计算我们可以知道，冒泡有两层嵌套，需要$O(n^2)$时间；归并排序需要$O(n log⁡n)$时间。

极简分析法：

      T(n)            拆分 n/2, 归并 n/2 ，一共是n/2 + n/2 = n
     /    \            以下依此类推：
   T(n/2) T(n/2)      一共是 n/2*2 = n
  /    \ /     \
 T(n/4)    ...........   一共是 n/4*4 = n

一共有$\log(n)$层，故复杂度是 $O(n \log n)$

下面给出图示案例：

代码

数据生成

//----------------------------------------------------
//数据生成
//data.cpp
#include <iostream>
#include <cstdlib> 
#include <ctime>
using namespace std;
void Random(int *a,int n,int l,int r)//生成范围在l~r的随机数 
{
    srand(time(0));  //设置时间种子
    for(int i=0;i<n;i++){
        a[i]=rand()%(r-l+1)+l;//生成区间r~l的随机数  
        if(a[i]*a[i-1]>0)
            a[i]*= a[i-1];//这里复杂化 
    }
}
void Print(int *a,int n)
{
    FILE *fp=fopen("data.txt","w");
    for(int i=0;i<n;i++)
        fprintf(fp,"%d\n",a[i]);
}
int main()
{
    
    int n=100000;//数组元素的个数，即生成随机数的个数
    int a[n];
    Random(a,n,1,32767);//生成随机数范围为0~32767
    Print(a,n);
    printf("生成好啦！现在有%d个随机数在data.txt里！\n整完了，睡觉去了~",n); 
    return 0;
}

冒泡排序

//----------------------------------------------------
//冒泡排序
//bubblesort.cpp
#include <iostream>
#include <cstdlib> 
#include <ctime>
using namespace std;
//---数据输入和输出---
int scan(int *data,int n)
{
    FILE *fp=fopen("data.txt","r");
    for(int i=0;i<n;i++)
        fscanf(fp,"%d",&data[i]);
    return 0;
}
int print(int *data,int n)
{
    FILE *fp=fopen("ans_bubble.txt","w");
    for(int i=0;i<n;i++)
        fprintf(fp,"%d\n",data[i]);
    return 0;
}

//正经冒泡
int sort(int *data,int n)
{
    int temp;
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(data[i] > data[j])
            {
                temp = data[i];
                data[i]=data[j];
                data[j]=temp;
            }
    return 0;
}
int main()
{
    int n;
    n=100000;//数据个数 
    int data[n];
    printf("啵啵啵~冒泡中……\n"); 
    scan(data,n);
    sort(data,n);
    print(data,n);
    printf("累了，原来乱七八糟的%d个数已经整整齐齐排好序放在ans_bubble.txt里啦！",n); 
    return 0;
}

归并排序

//----------------------------------------------------
//归并
//mergesort.cpp
#include <iostream>
#include <cstdlib> 
#include <ctime>
using namespace std;
//---数据输入和输出---
int scan(int *data,int n)
{
    FILE *fp=fopen("data.txt","r");
    for(int i=0;i<n;i++)
        fscanf(fp,"%d",&data[i]);
    return 0;
}
int print(int *data,int n)
{
    FILE *fp=fopen("ans_mergesort.txt","w");
    for(int i=0;i<n;i++)
        fprintf(fp,"%d\n",data[i]);
    return 0;
}
//-----正儿八经的二分归并排序-----
void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }
    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
    for(i=left_low;i<=left_high;i++)
        tmp[k++] = arr[i];
    }
    if(right_low <= right_high){
    //若第二个序列有剩余，直接复制出来粘到合并序列尾
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }
    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        merge_sort(arr, first, mid);
        merge_sort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}
//------以下为主函数------
int main()
{
    int n;
    n=100000;//数据个数 
    int data[n];
    printf("数据排序没烦恼，二分排序整！挺！好！\n二分排序今天就要让你看看这速度行不行~\n");
    scan(data,n);
    merge_sort(data,0,n);
    printf("才%d个数？就这？快打开ans_mergesort.txt看我的成果！",n); 
    print(data,n);
    return 0;
}

总结与心得

可以看到冒泡算法与归并排序在对于大数量级的数据的处理时间上差别巨大。对于10W的规模，冒泡的20余秒还在可以接受的范围内，但当仅仅扩大了5倍，规模来到50W的时候，冒泡排序需要的时间竟达到惊人的10分钟。而归并算法依旧以毫秒的时间计量完成了排序。

主观感知上，$n^2$ 与 $n \log n$ 差别好像不是很大，但实验结果告诉我们：对于大的数据规模，任何微小的不同都会引起近乎不啻天渊的差别。

不仅仅去依靠感知，而动手去做；不要小看些许差别，而精细入微。这个道理不仅存在于算法这项自科之中，也会成为我们学习处事的启示……