算法-归并排序-自顶向下

算法步骤：
自顶向下—递归法，函数调用自身一层套一层

1.动画演示

动画来自

https://www.runoob.com/w3cnote/merge-sort.html

其实我个人认为这个动图做的并不直观，至少缺少了明显的分段过程。归并更像是把一份完整的数据分段，二分分出很多小小段出来，再对小小段进行排序组合成小段，以此类推，小段最终再整合成一份完整的数据。

2.代码

整体使用模板，自适应int float型

gSort.h

#ifndef GSORT_H__
#define GSORT_H__
/*** get the size of array* arr: array address*/
#define gSizeof(arr) (sizeof(arr)/sizeof(*arr))/*** 交换两个数的值* @tparam T* @param a 数1* @param b 数2*/
template<typename T>
void gSwap(T &a,T &b)
{T temp=a;a=b;b=temp;
}//在本文的优化1被使用到
/***  插入排序优化版-只排序位置在l~r的内容* @note  example:*          int a[]={0,10,5,4,8,4,5};*          gInsertionSortAdvance(a,2,4,1);*          a---={0,10,8,5,4,4,5}* @param arr arr address* @param l left number* @param r right number* @param order 0: min~max 1: max~min*/
template<typename T>
void gInsertionSort(T *arr, int l,int r, bool order) {for(int i=l+1;i<=r;i++){T e=arr[i];//存储当前需要比较的变量int j;for(j=i;j>l;j--){if(order==0) {if(e<arr[j-1]) arr[j]=arr[j-1]; else break;}else {if(e>arr[j-1]) arr[j]=arr[j-1];else break;}}arr[j]=e;}
}/*** 归并排序-一分为二后判断大小合并两个数组* @tparam T* @param l left* @param r right* @param order 0: min~max 1: max~min*/
template<typename T>
void __gMerge(T *arr, int l,int mid,int r,bool order) {T aux[r-l+1];//开辟一份同样大小的存储空间for(int i=l;i<=r;i++)//将上面的空间赋值，实现复制{aux[i-l]=arr[i];}int i=l;int j=mid+1;//定义两个部分的标记点，初始化为头部位置for(int k=l;k<=r;k++){if(i>mid){// 如果左半部分元素已经全部处理完毕,防止越界arr[k]=aux[j-l];j++;}else if(j>r){ // 如果右半部分元素已经全部处理完毕,防止越界arr[k]=aux[i-l];i++;}else if(order==0){if(aux[i-l]<aux[j-l]) {arr[k] = aux[i - l];i++;}//判断大小赋值else {arr[k]=aux[j-l];j++;}}else //order==1{if(aux[i-l]>aux[j-l]) {arr[k] = aux[i - l];i++;}//判断大小赋值else {arr[k]=aux[j-l];j++;}}}
}/*** 归并排序-使用的一分为二函数，递归使用* @tparam T* @param l left* @param r right* @param order 0: min~max 1: max~min*/
template<typename T>
void __gMergeSort(T *arr, int l,int r,bool order) {
#if 1 //是否使用优化1if( r - l <= 15){gInsertionSort(arr,l,r,order);return;}
#elseif(l>=r) return;
#endifint mid=(l+r)/2;//计算中间值__gMergeSort(arr,l,mid,order);//二分左半部分__gMergeSort(arr,mid+1,r,order);//二分右半部分#if 1 //是否使用优化2if(order==0) {if(arr[mid] > arr[mid+1])//优化，只有不满足顺序才继续__gMerge(arr,l,mid,r,order);//将排好序的两部分合并起来}else {if(arr[mid] < arr[mid+1])//优化，只有不满足顺序才继续__gMerge(arr,l,mid,r,order);//将排好序的两部分合并起来}
#else__gMerge(arr,l,mid,r,order);//将排好序的两部分合并起来
#endif}/*** 归并排序* @tparam T* @param arr arr address* @param n number* @param order 0: min~max 1: max~min*/
template<typename T>
void gMergeSort(T *arr, int n, bool order) {__gMergeSort(arr,0,n-1,order);//注意是0~n-1
}#endif

main.cpp

#include <iostream>
#include "gSort.h"
using namespace std;
int main() {int a[]={1,3,2,4,10};gMergeSort(a, gSizeof(a),0);//从小到大for(int i=0;i< gSizeof(a);i++){cout << a[i]<<" ";}cout << endl;gMergeSort(a, gSizeof(a),1);//从大到小for(int i=0;i< gSizeof(a);i++){cout << a[i]<<" ";}
}

3.分析

• 算法复杂度O(nlogn)，数据量大时运算时间相较于O(n2)的算法有了显著提升
• 但由于算法复杂度本身前面是有系数的，数据量越小，系数值影响越大，这也会导致O(nlogn)的算法在某些情况可能还比不过O(n2)的

这里用条件编译使用了两处优化

1.优化1

由于数据量小时存在O(n2)算法更好的情况，所以在分段数据量小于15时采用插入排序法
插入排序法代码可以看算法-插入排序

2.优化2

默认是不管数据怎样都会进行排序合并，但是有时数据已经正常，不需要再排了，就可以直接跳过
实现效果类似于插入排序的优化
推荐优化2使用开启