文档介绍：cqs_2012
experiments to theory and person puter
算法之排序-----排序第二篇归并排序
分类: C++ 算法 2013-12-17 22:44 164人阅读评论(0) 收藏举报
c++排序算法归并排序
归并排序
引言
  这是我学习总结排序算法的第二篇---归并排序,归并排序还是蛮快
的。今天也是蛮高心的一天,写归并排序的代码,一次也没有调试,可
能因为程序比较小和自己比较熟悉吧,不过可以肯定的是往后要向这种
方向要求和发展自己。
算法
  算法描述
  归并操作的过程如下:
1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存
放合并后的序列
2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空
间,并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
  时间复杂度O(n*log n),空间复杂度O(n)。
  举个例子跑过程吧,这是最好的学习方法。
各标识符初始化如下,R = (S + E)/2 .
接着,如下(截图不太平,不好看哈)
         
接着如下
                       
接着,如下
                                   
接着,如下
1
接着合并,如下(选的例子数据不好,没能体现出改变来。。。。
痛。。)
                        
接着合并,如下                    
接着合并,如下
     
接着合并,如下
ok,完毕。
实验
       
代码
#include<iostream>
#include<>
#include<ctime>
using namespace std;
// function declare
template<class T>
void MergeSort( T data[], size_t s,size_t r, size_t e );
template<class T>
void Partition( T data[], size_t s, size_t e );
size_t const size = 1000000;
int main( )
{
DWORD time_s, time_e;
int * mydata = new int [size] ;
for(size_t i = 0; i < size; i++)
2
{
mydata[i] = rand() % 1000;
}
cout<<"给"<<size<<"个数据排序"<<endl;
time_s = GetTickCount();
Partition(mydata,0,size-1);
time_e = GetTickCount();
/*
for(size_t i = 0; i < size; i++