/*  * mergeSort.cpp  *  合并排序算法，算法导论P.17  *  Created on: 2011-12-21  *      Author: LiChanghai */ //#include 
     
       #include 
      
        #include 
       
         using namespace std; #define FLT_MAX 1.0E38 //定义一个很大的值作为哨兵 //对于待排序的数组 A[p...r], 其子数组A[p...q]，A[q+1...r]已排好序 //函数 subMerge(A, p, q, r), 将两个已排好序的子数组A[p...q]，A[q+1...r] //合并成一个有序的数组代替当前的数组A[p...r] template
        
          void subMerge(vector
         
           &array,                          typename vector
          
           ::iterator iterBegin, typename vector
           
            ::iterator iterBarrier, typename vector
            
             ::iterator iterEnd) { //创建两个数组，分别存放以iterBarrier为界线的array的左边部分和右边部分 vector
             
               arrayLeft(iterBegin, iterBarrier+1); vector
              
                arrayRight(iterBarrier+1, iterEnd); //在两个数组尾部分别放一个“哨兵” T temp = T(FLT_MAX); arrayLeft.push_back(temp); arrayRight.push_back(temp); //定义分别指向两个数组的迭代器 typename vector
               
                ::iterator iterLeft = arrayLeft.begin(); typename vector
                
                 ::iterator iterRight = arrayRight.begin(); //定义指向原数组array的迭代器 typename vector
                 
                  ::iterator iterArray = iterBegin; for(; iterArray != iterEnd; ++iterArray) if(*iterLeft < *iterRight) //如果左边小，将左边的值放入原数组 { *iterArray = *iterLeft; ++iterLeft; } else //如果右边小，将右边的值放入原数组 { *iterArray = *iterRight; ++iterRight; } return; } //函数 mergeSort(A, p, r) 调用subMerge对任意数组排序，p, r为下标 //mergeSort(A, p, r)首先将数组A分为两部分 //然后递归调用其本身对这两部分 分别排序 //依次递归下去，直到只剩2个数的时候完成这两个数的排序 //然后再层层返回调用处，将已排好序的子序列合并成更大的有序序列 //最后一次调用subMerge时完成数组的排序 template
                  
                    void mergeSort(vector
                   
                     &vec, typename vector
                    
                     ::iterator iterHead, typename vector
                     
                      ::iterator iterTail) { //测试 mergeSort 调用了多少次 //static int times_mergeSort=0; //cout<<"the "<<++times_mergeSort<<" call mergeSort()"<
                      
                       ::size_type halfLength = (vec.size()-1)/2; //数组长度的一半（正确方法） typename vector
                       
                        ::difference_type halfLength=( (iterTail-iterHead)-1)/2; //定义一个迭代器指向数组 vec 中间位置 typename vector
                        
                         ::iterator iterDivide = iterHead + halfLength; mergeSort(vec, iterHead, iterDivide+1); //递归调用自身对前半段排序 mergeSort(vec, iterDivide+1, iterTail); //递归调用自身对后半段排序 //cout<<"the "<<++times_subMerge<<" call subMerge()"<
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

    之前在计算数组中间位置的时候，瓜戳戳的用 size_type halfLength = (vec.size()-1)/2

结果只有1个或2个数排序的时候正确，当大于等于3个数时程序总是崩溃，一直检查下面递归调用有没有问题，

看了很久很久也没发现问题，百思不得其解，于是写3个数对程序一句一句的写出来分析，结果错的这么幼稚，

vec.size()是一个恒定的值，所以。。。。。哎，正确的方法是用两个迭代器的差计算子数组的长度，如下：

typename vector<T>::difference_type halfLength=( (iterTail-iterHead)-1)/2