归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。
#include<iostream>
using namespace std;
#include<algorithm>
//合并两个有序数组
void MemeryArray(int a[],int la,int b[],int lb,int c[])
{
int i=0, j=0, k=0;
while (i < la && j < lb)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while(i < la)
c[k++] = a[i++];
while (j < lb)
c[k++] = b[j++];
}
void test()
{
int a[] = { 1,5,8 };
int b[] = { 2,3,6,10,12 };
int c[8];
MemeryArray(a, 3, b, 5,c);
for_each(c, c + 8, [](int val) {cout << val << " "; });
}
int main()
{
test();
return 0;
}
一,概念及其介绍
二、适用说明
三、过程图示
归并排序是递归算法的一个实例,这个算法中基本的操作是合并两个已排序的数组,取两个输入数组 A 和 B,一个输出数组 C,以及三个计数器 i、j、k,它们初始位置置于对应数组的开始端。 A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置,相关计数器向前推荐一步。 当两个输入数组有一个用完时候,则将另外一个数组中剩余部分拷贝到 C 中。
#include<iostream>
using namespace std;
#include<algorithm>
//合并两个有序序列
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i =first, j = mid+1, k = 0;
while (i <=mid && j <=last)
{
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <=mid)
{
temp[k++] = a[i++];
}
while (j <=last)
{
temp[k++] = a[j++];
}
//最后把temp里面存放的合并后为有序的左右序列倒回原数组a
//注意a的起点
for (int i = 0; i < k; i++)
{
a[first+i] = temp[i];
}
}
//拆分数组,有序合并
void mergesort(int a[],int first,int last,int temp[])
{
//没有拆分到只剩一个元素的极小序列
if(first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp);//拆分左边序列,合并为有序序列
mergesort(a, mid + 1, last, temp);//拆分右边序列,合并为有序序列
mergearray(a, first, mid, last, temp);//将左序列和右序列合并为一整个有序序列
}
}
//归并排序主函数
void MergeSort(int a[],int n)
{
int* p = new int[n];
if (!p)
return;
mergesort(a,0,n-1,p);
delete[] p;
}
void test()
{
int a[] = { 1,3,5,2,7,9,10 };
MergeSort(a, 7);
for_each(a, a + 7, [](int val) {cout << val << " "; });
}
int main()
{
test();
return 0;
}
#include<iostream>
using namespace std;
#include<algorithm>
//合并两个有序序列
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i =first, j = mid+1, k = 0;
while (i <=mid && j <=last)
{
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i<=mid)
{
temp[k++] = a[i++];
}
while (j <=last)
{
temp[k++] = a[j++];
}
//最后把temp里面存放的合并后为有序的左右序列倒回原数组a
//注意a的起点
for (int i = 0; i < k; i++)
{
a[first+i] = temp[i];
}
}
//拆分数组,有序合并
void mergesort(int a[],int first,int last,int temp[])
{
//迭代的实现是直接从最小子序列(含一个元素)开始往上两两合并
int k = 1;//子序列长度
int Last=0;
int First=0;
int mid=0;
while (k<last)
{
First =0;
//3.剩余大于等于两个子序列的元素个数
while (First<=last-2*k+1)//加一的原因是因为下标从0算起
{
mid = First + k - 1;
Last = First + 2 * k - 1;
mergearray(a, First, mid, Last, temp);
First += 2 * k;
}
//当剩下的没有合并处理过的元素数量不足2k,即无法构成两个子序列进行合并操作时,要分类处理
//1.剩下小于等于一个子序列的元素个数
if (last-First<=k)
{
mid = First + (last - First) / 2;
mergearray(a, First, mid, last, temp);
}
//2.剩下大于一个小于两个的子序列元素个数
else
{
mid = First + k - 1;;
mergearray(a,First, mid, last, temp);
}
k *= 2;
}
//说明此时是特殊奇数情况,数组末尾还单着一个元素没有于前面一个完整的子序列合并
if (First==last)
{
mergearray(a, first, last - 1, last, temp);
}
}
//归并排序主函数
void MergeSort(int a[],int n)
{
int* p = new int[n];
if (!p)
return;
mergesort(a,0,n-1,p);
delete[] p;
}
void test()
{
int a[] = { 3,4,5,6,1,2,7,9,32,6,89,0,5,21,56,22,0,3,1};
MergeSort(a,19);
for_each(a, a+19, [](int val) {cout << val << " "; });
}
int main()
{
test();
return 0;
}
(1)剩下小于等于一个子序列的元素个数
(2)剩下大于一个小于两个的子序列元素个数
(3)剩余大于等于两个子序列的元素个数
(4)特殊奇数情况,数组末尾还单着一个元素没有于前面一个完整的子序列合并