归并排序算法

算法描述

归并操作的过程如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

#include <iostream>

#include <string>
#include <algorithm>


using namespace std;


//归并排序，升序。


void Merge(int a[],int b[],int left,int mid,int right)
{
int k = left;
int i;
int begin1 = left;
int end1 = mid;
int begin2 = mid+1;
int end2 = right;
while(begin1<=end1&&begin2<=end2)
{
if(a[begin1]<=a[begin2])
{
b[k++] = a[begin1];
begin1++;
}
else
{
b[k++] = a[begin2];
begin2++;
}
}
//第一段没有比较完的情况
if(begin1<=end1)
{
for(i = begin1;i<=end1;i++)
b[k++] = a[i];
}
//第二段还没有比较完的情况
else
{
for(i = begin2;i<=end2;i++)
b[k++] = a[i];
}
}


void MergePass(int a[],int b[],int seg,int size)
{
int seg_start_index = 0;
int i;
while(seg_start_index<=size-2*seg)//可满足两两合并的最低界限值
{
Merge(a,b,seg_start_index,seg_start_index+seg-1,seg_start_index+2*seg-1);
seg_start_index += 2*seg;
}
//如果一段刚好是可以合并的长度，另一段则少于正好可和并的长度
if(seg_start_index+seg<size)
{
Merge(a,b,seg_start_index,seg_start_index+seg-1,size-1);
}
//如果正好只剩一段或者少于一段的长度
else
{
for(i = seg_start_index;i<size;i++)
b[i] = a[i];
}
}


void Merge_Sort(int a[],int size)
{
int seg;//需要排序合并的段的大小
int *tmp = new int[size];
seg = 1;
while(seg<size)
{
MergePass(a,tmp,seg,size);
seg +=seg;
MergePass(tmp,a,seg,size);
seg += seg;
}
}


int main()
{
int num[] = {1,4,6,2,8,7,3,5,9,0};
int i;
Merge_Sort(num,sizeof(num)/sizeof(num[0]));
for(i = 0;i<sizeof(num)/sizeof(num[0]);i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
return 0;
}

最后

以上就是勤奋小天鹅为你收集整理的归并排序算法的全部内容，希望文章能够帮你解决归并排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。