归并排序

引言 这是我学习总结排序算法的第二篇---归并排序，归并排序还是蛮快的。今天也是蛮高心的一天，写归并排序的代码，一次也没有调试，可能因为程序比较小和自己比较熟悉吧，不过可以肯定的是往后要向这种方向要求和发展自己。 算法

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾 时间复杂度O(n*log n)，空间复杂度O（n）。 举个例子跑过程吧，这是最好的学习方法。
   各标识符初始化如下，R = （S + E）/2 .
   接着，如下（截图不太平，不好看哈） 接着如下
   接着，如下
   接着，如下
   < http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/49/1_juut9__.jpg" alt="\">
   
   接着合并，如下（选的例子数据不好，没能体现出改变来。。。。痛。。） 接着合并，如下
   接着合并，如下
   接着合并，如下
   ok，完毕。 实验
   代码 test.cpp
   

   #include
        
         
   #include
         
           #include
          
            using namespace std; // function declare template
           
             void MergeSort( T data[], size_t s,size_t r, size_t e ); template
            
              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++) { mydata[i] = rand() % 1000; } cout<<"给"<
             
               void Partition( T data[], size_t s, size_t e ) { if( data != NULL && s < e ) { size_t r = (s + e)/2 ; Partition(data,s,r) ; Partition(data,r+1,e) ; MergeSort(data,s,r,e) ; } } template
              
                void MergeSort( T data[], size_t s,size_t r, size_t e ) { if( data != NULL && s <= r && r <= e ) { T * my = new T[e - s + 1] ; size_t L = s ; size_t R = r + 1 ; size_t my_it = 0; while( L <= r && R <= e ) { if( data[L] <= data[R] ) my[my_it++] = data[L++]; else my[my_it++] = data[R++]; } while( L <= r ) { my[my_it++] = data[L++]; } while( R <= e ) { my[my_it++] = data[R++]; } for(L = 0; L < (e - s + 1); L++) { data[ L+s ] = my[L]; } } }