并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。合并排序法是将兩個(或兩個以上)有序表合并成一個新的有序表,即把待排序序列分為若幹個子序列,每個子序列是有序的。然後再把有序子序列合并為整體有序序列。将已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序,合并排序也叫歸并排序。
1、遞歸實作的合并排序
#include <iostream>
#include <stdio.h>
using namespace std;
int a[] = {10,5,9,4,3,7,8};
int b[7];
template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r);
template <class Type>
void MergeSort(Type a[],int left,int right);
int main()
{
for(int i=0; i<7; i++)
cout<<a[i]<<" ";
cout<<endl;
MergeSort(a,0,6);
for(int i=0; i<7; i++)
cout<<a[i]<<" ";
cout<<endl;
}
template <class Type>
void Merge(Type c[],Type d[],int l,int m,int r)
{//合并c[l:m]和c[m+1:r]到d[l:r]
int i = l,j = m + 1,k = l;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[k++] = c[i++];
else
d[k++] = c[j++];
}
if(i>m)
{
for(int q=j; q<=r; q++)
d[k++] = c[q];
}
else
{
for(int q=i; q<=m; q++)
d[k++] = c[q];
}
}
template <class Type>
void MergeSort(Type a[],int left,int right)
{//遞歸合并
if(left<right)
{
int i = (left + right)/2;
MergeSort(a,left,i);
MergeSort(a,i+1,right);
Merge(a,b,left,i,right);//合并到數組b
//複制回數組a
for(int g=left; g<=right; g++)
a[g] = b[g];
}
}
2、合并排序非遞歸實作
從分支政策機制入手,可消除程式中的遞歸。非遞歸實作的大緻思路是先将數組a中元素兩兩配對,用合并算法将它們排序,構成n/2組長度為2的排好的子數組段,然後再将它們排成長度為4的排好序的子數組段,如此繼續下去,直到整個數組排好序。
(即:二路歸并排序:見點選打開連結)