归并排序

归并排序(Merge Sort)
并归排序利用了递归的思想,把数组分割成很多小的数组序列,然后两两合并,最终整个数组有序.因为递归到一个子数组序列只有一个元素时,然后将这样的数组合并就得到2个元素的有序数组,依次类推.
//合并两个子数组序列,以mid为中间点,begin,end为前后界限,分割成两个子序列.
void MergeSortedArr(int* arr, int begin , int mid , int end, int* tmpArr)
{
  int lBegin = begin; //左边序列的起始索引号
  int lEnd   = mid;   //左边序列的最后索引号
  int rBegin = mid + 1;
  int rEnd   = end;
  int k = 0;  //两个子序列元素个数之和
  while( lBegin <= lEnd && rBegin <= rEnd) //当有一个子序列遍历完了退出循环
     {
         if(arr[lBegin] <= arr[rBegin])
             tmpArr[k++] = arr[lBegin++];
         else
           tmpArr[k++] = arr[rBegin++];
     }
   while(lBegin <= lEnd)
      tmpArr[k++] = arr[lBegin++];
   while(rBegin <= rEnd)
     tmpArr[k++] = arr[rBegin++];
 
for(int i = 0; i < k; i++)
  arr[begin + i] = tmpArr[i];
}
 
void MegerSort(int* arr, int begin , int end, int* tmpArr)
{
   if( begin < end)
     {
        int mid = (begin + end) /2;
       MergeSort(arr, begin , mid , tmpArr) ; //将左边序列排序
       MergeSort(arr, mid + 1, end, tmpArr); //将右边序列排序
       MergeSortedArr(arr, begin , mid, end, tmpArr); //合并两个序列
     }
}
 
测试代码:
int arr[] = { 1,3,2,4,5,7,6,8,9};
int len = sizeof(arr)/sizeof(int);
int* tmpArr = new int[len];
MergeSort(arr, 0, len - 1, tmpArr);
delete []tmpArr;

补充：综合编程 , 其他综合 ,

上一个：嵌入式中程序升级,使用ftp shell脚本,方式
下一个：Vim的文件加密与解密