MT5(C++)软件编程-归并排序算法

1. MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
2. MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
3. MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
4. MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
5. MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
6. MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
7. MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
8. MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
9. MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
10. MT5(C++)软件编程十大排序算法 - 基数排序算法 (radix Sort)

归并排序算法
以二分之一分递归分割数组
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template<typename T> 
void mergeSort(T &arr[], const bool seq = true) {
    int len = ArraySize(arr);
    T b[];
    ArrayResize(b,len);
    if(seq)
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = merge_min(start + seg, len), high = merge_min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            while (start1 < end1)
                b[k++] = arr[start1++];
            while (start2 < end2)
                b[k++] = arr[start2++];
        } 
        T temp[];
        ArrayResize(temp,len);
        ArrayCopy(temp,arr);
        ArrayCopy(arr,b);
        ArrayCopy(b,temp);
    }
    else
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = merge_min(start + seg, len), high = merge_min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = arr[start1] > arr[start2] ? arr[start1++] : arr[start2++];
            while (start1 < end1)
                b[k++] = arr[start1++];
            while (start2 < end2)
                b[k++] = arr[start2++];
        } 
        T temp[];
        ArrayResize(temp,len);
        ArrayCopy(temp,arr);
        ArrayCopy(arr,b);
        ArrayCopy(b,temp);
    }
    //if (a != arr) {
    //    for (int i = 0; i < len; i++)
    //        b[i] = a[i];
    //    b = a;
    //}
}

归并递归排序算法
以二分之一分递归分割数组
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template<typename T>
void mergeSort2(T &arr[], const bool seq = true) 
{
    int len = ArraySize(arr);
    T reg[];
    ArrayResize(reg,len);
    _merge_sort_recursive(arr, reg, 0, len - 1,seq);
}

template<typename T>
void _merge_sort_recursive(T &arr[], T &reg[], int start, int end,bool seq = true) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    _merge_sort_recursive(arr, reg, start1, end1,seq);
    _merge_sort_recursive(arr, reg, start2, end2,seq);
    int k = start;
    if(seq)
    {
      while (start1 <= end1 && start2 <= end2)
          reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
      while (start1 <= end1)
          reg[k++] = arr[start1++];
      while (start2 <= end2)
          reg[k++] = arr[start2++];
      for (k = start; k <= end; k++)
          arr[k] = reg[k];
    }
    else
    {
      while (start1 <= end1 && start2 <= end2)
          reg[k++] = arr[start1] > arr[start2] ? arr[start1++] : arr[start2++];
      while (start1 <= end1)
          reg[k++] = arr[start1++];
      while (start2 <= end2)
          reg[k++] = arr[start2++];
      for (k = start; k <= end; k++)
          arr[k] = reg[k];
    }
    
}