数据结构基础(5) --归并排序

时间:2021-06-24 10:41:36

归并排序的基本思想:

    将两个或两个以上的有序子序列”归并”为一个有序序列:假定待排序表含有n个记录, 则可以看成是n个有序的子表, 每个子表长度为1, 然后两两归并, 得到[n/2]个长度为2或1的有序表,; 再量量归并, ...., 如此重复, 直到合并成为一个长度为n的有序表为止, 这种排序方法称为2-路归并排序.如图为一个2-路归并排序的一个示例:

数据结构基础(5) --归并排序

[cpp]  view plain copy 数据结构基础(5) --归并排序 数据结构基础(5) --归并排序
  1. /**说明: 
  2.     将有序的记录序列 initList[left:mid] 和 initList[mid+1:right]归并为有序的记录序列 initList[left:right] 
  3.     initList:  原始的有序序列[分为两段] 
  4.     tmpList:     合并过程中需要的中间序列 
  5.     left:       initList最左边元素的下标 
  6.     mid:        指向第一个有序序列的最后一个元素的下标 
  7.     right:      initList最右边元素的下标 
  8. */  
  9. template <typename Type>  
  10. int Merge(Type *initList, Type *tmpList, int left, int mid, int right)  
  11. {  
  12.     //先将待归并的数组复制到tmpList中去  
  13.     std::copy(initList+left, initList+right+1, tmpList+left);  
  14. //    同下:  
  15. //    for (int i = left; i <= right; ++i)  
  16. //    {  
  17. //        tmpList[i] = initList[i];  
  18. //    }  
  19.   
  20.     int s1 = left, s2 = mid+1;  
  21.     int iResult = left;  
  22.     while (s1 <= mid && s2 <= right)  
  23.     {  
  24.         if (tmpList[s1] <= tmpList[s2])  
  25.         {  
  26.             initList[iResult ++] = tmpList[s1 ++];  
  27.         }  
  28.         else  
  29.         {  
  30.             initList[iResult ++] = tmpList[s2 ++];  
  31.         }  
  32.     }  
  33.   
  34.     int *end;  
  35.     if (s1 <= mid)  
  36.         end = std::copy(tmpList+s1, tmpList+mid+1, initList+iResult);  
  37.     if (s2 <= right)  
  38.         end = std::copy(tmpList+s2, tmpList+right+1, initList+iResult);  
  39.     return end - (initList+left);  
  40.   
  41. //    同下:其实这两个循环只有一个会执行  
  42. //    while (s1 <= mid)  
  43. //    {  
  44. //        initList[iResult ++] = tmpList[s1 ++];  
  45. //    }  
  46. //    while (s2 <= right)  
  47. //    {  
  48. //        initList[iResult ++] = tmpList[s2 ++];  
  49. //    }  
  50. //  
  51. //    return iResult;  
  52. }  
[cpp]  view plain copy 数据结构基础(5) --归并排序 数据结构基础(5) --归并排序
  1. //二路归并排序-递归算法  
  2. template <typename Type>  
  3. void mergeSort(Type *initList, Type *tmpList, int left, int right)  
  4. {  
  5.     if (left >= right)  
  6.         return;  
  7.   
  8.     int mid = (left+right)/2;  
  9.     mergeSort(initList, tmpList, left, mid);    //先将左边元素排序  
  10.     mergeSort(initList, tmpList, mid+1, right); //后将右边元素排序  
  11.     Merge(initList, tmpList, left, mid, right); //合并  
  12. }  

可以看出对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即:

    (1)每一趟归并(合并)的时间复杂度为 O(n);

    (2)总共需进行[logn]趟。