本文共 960 字，大约阅读时间需要 3 分钟。

归并排序 -

采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素，再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。

时间复杂度：O(NlogN) 　　稳定性：稳定

/*归并排序*///排序两个有序数列void mergeSortInOrder(vector
   
     &arr, int bgn, int mid, int end){
       int *pBuf = new int[end - bgn];    int *pTemp = pBuf;    int lindex = bgn;    int rindex = mid;    while ((lindex < mid) && (rindex < end))        *(pTemp++) = (arr[lindex] < arr[rindex]) ? arr[lindex++] : arr[rindex++];    while (lindex < mid)        *pTemp++ = arr[lindex++];    while (rindex < end)        *pTemp++ = arr[rindex++];    //pTemp -> arr    pTemp = pBuf;    for (int i = bgn; i < end; i++)        arr[i] = *pTemp++;    delete []pBuf;}//UpToDown To DownToUpvoid mergeSort(vector
    
      &arr, int bgn, int end){
       //数组arr空or仅有一个元素则退出    if (bgn >= end - 1)        return;    int mid = (bgn + end) / 2;    mergeSort(arr, bgn, mid);    mergeSort(arr, mid, end);    mergeSortInOrder(arr, bgn, mid, end);}
    
   

转载地址：http://pimqf.baihongyu.com/