|
在自己摸爬滚打前行或是后退的时候，总会出现很多的惊喜或意外
楼主大三狗，前些天异想天开想面试青少年编程老师一职
没想到对面坐的是科大讯飞十年辞职创业的高级攻城狮。。。
很尬，未果。我说了近况，并没有潜心研究算法云云，一直在入门机器学习，深度学习
他说本科生在没有能力的情况下不要研究这些……最好学学算法，以后出来找工作肯定是不成问题的。。
前言背景有点长，下面正式开始
归并排序是一种高效率的算法，时间复杂度只有O(nlogn）
它的核心思想是分治策略
如下图，分是将其二分至不可再分
分完需要再合，合的方法是如下
俩俩互相比较大小，做好排序，这里的已经合并的还剩下最后一步。
到了思想关键的地方了，如何给这些进行排序呢？
需要创建一个数组，来保存原数组信息，在拿拷贝的数组进行对原数组进行修改，即排序
需要建立三个游标，如下：
下面一行为拷贝数组，将两端进行比较，设左端为起始为l，末端为mid；右端起始即为mid+1，末端为r
设遍历游标为i，j
取第一个元素比较做范例，若arr[l] < arr[mid+1] 则将原数组a[k] = arr[l]值即可
所以大致分类如下：
1.如果 i > mid，则说明左端遍历已结束；
2.如果j > r，则说明右端遍历已结束；
3.如果上述两者都不满足，则说明两端遍历都没有结束，则比较arr与arr[j]的关系即可
3.1. 若arr > arr[j] ,则原数组a[k] = arr[j] ，此时 j ++ ，k++，j，k自增，游标向右移；
3.2 .若arr < arr[j] ,则原数组a[k] = arr ， 此时 i ++ ，k ++，i，k自增，游标向右移。
贴出代码，困于递归很久，毕竟接触的少
大家如果有对递归不熟悉的可以在函数里多使用printf函数来进行输出，探测函数的走向
[C++] 纯文本查看 复制代码 //归并排序算法
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[r - l + 1]; //创建数组指针，新版可以直接使用变量创建，如下一行代码
//T aux[r - l + 1]; //创建一个数组
for (int i = l; i <= r; i++) //拷贝数组
{
aux[i - l] = arr[i];
printf("拷贝数组a[%d] = arr[%d] = %d \n", i - l, i, arr[i]);
}
int i = l, 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 (aux[i - l] < aux[j - l])
{
arr[k] = aux[i - l];
i++;
}
else
{
arr[k] = aux[j - l];
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);
}
语言组织比较乱。。
| 
发表于 2018-10-8 13:10
|
发表于 2018-10-8 18:50
