归并排序

引子：

看了归并排序，觉得这才真正像个算法，插入，选择，冒泡简直特么的就像是暴力猜解密码一样的弱。

测试了100000个随机数字的排序，比上述3个算法的运行时间少了近100倍的数量级。

算法思想：

归并排序的主要思路是分治，可以大概参考二分查找的思路，并且也是递归的方式。

首先按数组长度将数组切成左右两半，先将左边排序，再将右边排序，再将两边的合并起来，并且在合并的过程中排序，需要在栈中建立一个新的同样大小的数组用于缓存。

在每次拆分以后，有一个起点索引 nStart，一个中点索引 nMid，一个终点索引 nEnd，这时需要再次将nStart到nMid拆分成三个节点，直到nStart大于或等于nEnd，退出递归。

然后进行排序，递归的逻辑如下：

void MergeSort(int* ua, int nStart, int nEnd) 
{ 
    if(nStart >= nEnd) 
    { 
        return; 
    } 
    int nMid = nStart + (nEnd - nStart) / 2; 
 
    MergeSort(ua, nStart, nMid); 
    MergeSort(ua, nMid+1, nEnd); 
    Merge(ua, nStart, nMid, nEnd); 
} 

void MergeSort(int* ua, int nStart, int nEnd)
{
 if(nStart >= nEnd)
 {
  return;
 }
 int nMid = nStart + (nEnd - nStart) / 2;

 MergeSort(ua, nStart, nMid);
 MergeSort(ua, nMid+1, nEnd);
 Merge(ua, nStart, nMid, nEnd);
}

排序的过程需要借助一个临时数组用来合并，比较左边和右边数据的大小来选择性地插入数据，如果左边的全都插完了，就开始插右边的。但是判断左右是否插完的逻辑要先于插入数据的逻辑，代码如下：

void Merge(int* ua, int nStart, int nMid, int nEnd) 
{ 
    int a[N]; 
    int i = nStart; 
    int j = nMid + 1; 
 
    for (int k = nStart; k <= nEnd; k++) 
    { 
        a[k] = ua[k]; 
    } 
 
    for (int k = nStart; k <= nEnd; k++) 
    { 
        if(i > nMid) 
        { 
            ua[k] = a[j++]; 
        } 
        else if(j > nEnd) 
        { 
            ua[k] = a[i++]; 
        } 
        else if( a[j] < a[i]) 
        { 
            ua[k] = a[j++]; 
        } 
        else 
        { 
            ua[k] = a[i++]; 
        } 
    } 
} 

void Merge(int* ua, int nStart, int nMid, int nEnd)
{
 int a[N];
 int i = nStart;
 int j = nMid + 1;

 for (int k = nStart; k <= nEnd; k++)
 {
  a[k] = ua[k];
 }

 for (int k = nStart; k <= nEnd; k++)
 {
  if(i > nMid)
  {
   ua[k] = a[j++];
  }
  else if(j > nEnd)
  {
   ua[k] = a[i++];
  }
  else if( a[j] < a[i])
  {
   ua[k] = a[j++];
  }
  else
  {
   ua[k] = a[i++];
  }
 }
}

整体的代码量不大，但是需要想清楚整个递归过程和递归退出的条件。

假设一共10个随机数，从小到大排序：

第一步是按索引拆分，

先拆成0，1，2，3，4 和 5，6，7，8，9

再将0，1，2，3，4 拆分成 0，1，2 和 3，4

再将0，1，2，拆分成 0，1 和 2

0 和 1 不可以再拆了，于是开始对0，1进行排序

再对2进行排序，因为2只有一个数，所以直接跳过了。

完成后再将0，1 与 2 合到一起进行排序，

然后再对3，4进行排序。

再将0，1，2，3，4一起进行排序

最后将0，2，3，4，5，6，7，8，9一起排序

因为每次排序其实只是对两个数进行比较然后插入数组，所以速度是很快的。

测试代码如下：

#include "stdafx.h"  
#include "windows.h"  
#include "time.h"  
 
const int N = 10; 
int O = 0; 
 
int* GenRandom() 
{ 
    srand( (unsigned)time( NULL ) ); 
 
    int* a = new int[N]; 
    for (int i = 0; i < N; i++) 
    { 
 
        a[i] = rand() ; 
    } 
    return a; 
} 
 
SYSTEMTIME StartTime = {0}; 
FILETIME StartFileTime = {0}; 
SYSTEMTIME EndTime= {0}; 
FILETIME SEndFileTime= {0}; 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int* a = GenRandom(); 
    GetLocalTime(&StartTime); 
    printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds); 
 
    MergeSort(a,0,N-1); 
 
    GetLocalTime(&EndTime); 
    printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds); 
    printf("times %d \r\n", O); 
    return 0; 
} 

#include "stdafx.h"
#include "windows.h"
#include "time.h"

const int N = 10;
int O = 0;

int* GenRandom()
{
 srand( (unsigned)time( NULL ) );

 int* a = new int[N];
 for (int i = 0; i < N; i++)
 {

  a[i] = rand() ;
 }
 return a;
}

SYSTEMTIME StartTime = {0};
FILETIME StartFileTime = {0};
SYSTEMTIME EndTime= {0};
FILETIME SEndFileTime= {0};

int _tmain(int argc, _TCHAR* argv[])
{
 int* a = GenRandom();
 GetLocalTime(&StartTime);
 printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);

 MergeSort(a,0,N-1);

 GetLocalTime(&EndTime);
 printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);
 printf("times %d \r\n", O);
 return 0;
}

补充：软件开发 , C++ ,