—归并排序—
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
算法描述
具体算法描述如下：
<1>.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
<2>.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
<3>.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
<4>.重复步骤 3 直到某一指针达到序列尾；
<5>.将另一序列剩下的所有元素直接复制到合并序列尾。
代码实现
//合并
void Merge(int a[],int temp[], int left, int mid, int right)
{
//左第一个数游标
int l_pos = left;
//右第一个数游标
int r_pos = mid + 1;
//全局游标
int cur = left;
while (l_pos <= mid && r_pos <= right) // 当左游标小于中间值 并且 右游标小于末位置
{
if (a[l_pos] > a[r_pos]) // 如果 左边第一个元素 大于 右边第一个元素
temp[cur++] = a[r_pos++]; // 则 将右边的第一个元素放入临时列表里面
else
temp[cur++] = a[l_pos++]; // 否则将左边的第一个元素放入临时列表里面
}
while (l_pos <= mid) // 比较完后若左边有剩余 则将左边的数依次放入临时列表
temp[cur++] = a[l_pos++];
while (r_pos <= right)
temp[cur++] = a[r_pos++]; // 比较完后若右边有剩余 则将右边的数依次放入临时列表
while (left <= right) // 把临时列表的值赋给原先的列表
{
a[left] = temp[left];
left++;
}
}
//递归接口
void MergeSort(int a[],int temp[],int left,int right)
{
if (left < right) // 递归的终止条件
{
int mid = (left + right) / 2;
//拆分
//左半部分拆分
MergeSort(a, temp, left, mid);
//右半部分拆分
MergeSort(a, temp, mid+1, right);
//合并
Merge(a, temp, left, mid, right);
}
}
void Merge_Sort(int a[],int n)
{
int* temp = new int[n];
MergeSort(a,temp, 0, n-1);
delete[] temp;
}
算法分析
平均情况：T(n) = O(n2)
最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
稳定性
稳定
采用的是比较左右两边的最小值依次放入临时数组，故顺序不变
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
