排序算法之归并排序
在自己摸爬滚打前行或是后退的时候，总会出现很多的惊喜或意外楼主大三狗，前些天异想天开想面试青少年编程老师一职
没想到对面坐的是科大讯飞十年辞职创业的高级攻城狮。。。
很尬，未果。我说了近况，并没有潜心研究算法云云，一直在入门机器学习，深度学习
他说本科生在没有能力的情况下不要研究这些……最好学学算法，以后出来找工作肯定是不成问题的。。
前言背景有点长，下面正式开始
归并排序是一种高效率的算法，时间复杂度只有O(nlogn）
它的核心思想是分治策略
如下图，分是将其二分至不可再分
分完需要再合，合的方法是如下
俩俩互相比较大小，做好排序，这里的已经合并的还剩下最后一步。
到了思想关键的地方了，如何给这些进行排序呢？
需要创建一个数组，来保存原数组信息，在拿拷贝的数组进行对原数组进行修改，即排序
需要建立三个游标，如下：
下面一行为拷贝数组，将两端进行比较，设左端为起始为l，末端为mid；右端起始即为mid+1，末端为r
设遍历游标为i，j
取第一个元素比较做范例，若arr < arr则将原数组a = arr值即可
所以大致分类如下：
1.如果 i > mid，则说明左端遍历已结束；
2.如果j > r，则说明右端遍历已结束；
3.如果上述两者都不满足，则说明两端遍历都没有结束，则比较arr与arr的关系即可
3.1. 若arr > arr ,则原数组a = arr ，此时 j ++ ，k++，j，k自增，游标向右移；
3.2 .若arr < arr ,则原数组a = arr ， 此时 i ++ ，k ++，i，k自增，游标向右移。
贴出代码，困于递归很久，毕竟接触的少
大家如果有对递归不熟悉的可以在函数里多使用printf函数来进行输出，探测函数的走向
//归并排序算法
template<typename T>
void __Merge(T arr[], int l, int mid, int r)
{
printf("\n排序函数入口 l = %d, mid = %d, r = %d \n", l, mid, r);
T* aux = new T; //创建数组指针，新版可以直接使用变量创建，如下一行代码
//T aux; //创建一个数组
for (int i = l; i <= r; i++) //拷贝数组
{
aux = arr;
printf("拷贝数组a[%d] = arr[%d] = %d \n", i - l, i, arr);
}
int i = l, j = mid + 1; //将数组分成两部分进行比较
for (int k = l; k <= r; k++)
{
//判断位置合法性，左端已遍历结束
if (i > mid)
{
arr = aux;
j++;
}//判断位置合法性，右端遍历已结束
else if (j > r)
{
arr = aux;
i++;
}//合法情况，进行比较
else if (aux < aux)
{
arr = aux;
i++;
}
else
{
arr = aux;
j++;
}
}
delete []aux;
}
template<typename T>
void __MergeSort(T arr[], int l, int r)
{
if (l >= r)
return;
int mid = (l + r) / 2;
__MergeSort(arr, l, mid);
__MergeSort(arr, mid + 1, r);
__Merge(arr, l, mid, r);
}
template<typename T>
void MergeSort(T arr[], int n)
{
__MergeSort(arr, 0, n - 1);
}
语言组织比较乱。。
Bokjan 发表于 2018-10-8 13:58
“新版可以直接使用变量创建”是VLA，这是C的语言特性，C++标准中不包含，当然部分编译器扩展实现了这个。
DEV中可以实现，现在的新版好像可以支持，我用的VS2015不支持 曾经的梦想也是将当个初中小学的计算机老师 然而大学成绩没够去学了英语，转专业也没转成， 也只能看看吾爱的大佬发些教程学学这样子。 楼主可以的。。。 额外空间复杂度On的 算法头大 这个很高深啊。 “新版可以直接使用变量创建”是VLA，这是C的语言特性，C++标准中不包含，当然部分编译器扩展实现了这个。 澹泊明志 发表于 2018-10-8 13:37
额外空间复杂度On的
对的，大佬{:301_1003:} 感谢楼主分享！算法一直在学，就是有点难！楼主还是好厉害的！
页:
[1]
2