根據(jù)Merge Sort原理, 自己實(shí)現(xiàn)的歸并排序算法+詳細(xì)注釋+代碼(C#,C/C++) [分享]
本文是受前面的一篇《C#實(shí)現(xiàn)所有經(jīng)典排序算法》- 飛雪飄寒 影響，應(yīng)邀請(qǐng)，把我曾經(jīng)實(shí)現(xiàn)的歸并排序算法拿出來分享，歡迎改善：
歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。
1. 不多廢話,我已經(jīng)把注釋寫得很詳細(xì)了,C#實(shí)現(xiàn)的分享如下:
/// <summary>
/// 歸并排序之歸：歸并排序入口
/// Updated by Lihua at 05/06/2009
/// </summary>
/// <param name="data">無序數(shù)組</param>
/// <returns>有序數(shù)組</returns>
/// <author>lihua</author>
/// <copyright>www.zivsoft.com</copyright>
int[] Sort(int[] data)
{
//若data為null，或只剩下1 or 0個(gè)元素，返回，不排序
if (null == data || data.Length <= 1)
{
return data;
}
//取數(shù)組中間下標(biāo)
//int middle = data.Length / 2; //方法一：除2取整數(shù)
int middle = data.Length >> 1; //方法二：位移 (感謝讀者h(yuǎn)yper給出的這個(gè)效率稍高的方法)
//初始化臨時(shí)數(shù)組let,right，并定義result作為最終有序數(shù)組，若數(shù)組元素奇數(shù)個(gè)，將把多余的那元素空間預(yù)留在right臨時(shí)數(shù)組
int[] left = new int[middle], right = new int[data.Length - middle], result = new int[data.Length];
//下面這句對(duì)性能有些影響，所以在上面有了改進(jìn)，直接用data.Length-middle初始化right數(shù)組
//if (data.Length % 2 != 0) right = new int[middle + 1];
//int i = 0, j = 0;
//foreach (int x in data)//開始排序
//{
// if (i < middle)//填充左數(shù)組
// {
// left[i] = x;
// i++;
// }
// else//填充右數(shù)組
// {
// right[j] = x;
// j++;
// }
//}
//上面的foreach被改成了for循環(huán)
//for (int i = 0; i < data.Length; i++)
//{
// if (i < middle)//用middle，不用left.Length
// {
// left[i] = data[i];
// }
// else
// {
// right[i - middle] = data[i]; //此處i-middle，讓我省掉定義一個(gè)j，性能有所提高
// }
//}
//經(jīng)調(diào)查,用Array.Copy的確比上面的for循環(huán)優(yōu)化很多
Array.Copy(data, 0, left, 0, middle);//拷貝左數(shù)組
Array.Copy(data, left.Length, right, 0, right.Length); //拷貝右數(shù)組
left = Sort(left);//遞歸左數(shù)組
right = Sort(right);//遞歸右數(shù)組
result = Merge(left, right);//開始排序
//this.Write(result);//輸出排序,測(cè)試用(lihua debug)
return result;
}
/// <summary>
/// 歸并排序之并:排序在這一步
/// </summary>
/// <param name="a">左數(shù)組</param>
/// <param name="b">右數(shù)組</param>
/// <returns>合并左右數(shù)組排序后返回</returns>
int[] Merge(int[] a, int[] b)
{
//定義結(jié)果數(shù)組，用來存儲(chǔ)最終結(jié)果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左數(shù)組中元素小于右數(shù)組中元素
{
result[k++] = a[i++];//將小的那個(gè)放到結(jié)果數(shù)組
}
else//左數(shù)組中元素大于右數(shù)組中元素
{
result[k++] = b[j++];//將小的那個(gè)放到結(jié)果數(shù)組
}
}
while (i < a.Length)//這里其實(shí)是還有左元素，但沒有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，無左元素
{
result[k++] = b[j++];
}
return result;//返回結(jié)果數(shù)組
}
/// 歸并排序之歸：歸并排序入口
/// Updated by Lihua at 05/06/2009
/// </summary>
/// <param name="data">無序數(shù)組</param>
/// <returns>有序數(shù)組</returns>
/// <author>lihua</author>
/// <copyright>www.zivsoft.com</copyright>
int[] Sort(int[] data)
{
//若data為null，或只剩下1 or 0個(gè)元素，返回，不排序
if (null == data || data.Length <= 1)
{
return data;
}
//取數(shù)組中間下標(biāo)
//int middle = data.Length / 2; //方法一：除2取整數(shù)
int middle = data.Length >> 1; //方法二：位移 (感謝讀者h(yuǎn)yper給出的這個(gè)效率稍高的方法)
//初始化臨時(shí)數(shù)組let,right，并定義result作為最終有序數(shù)組，若數(shù)組元素奇數(shù)個(gè)，將把多余的那元素空間預(yù)留在right臨時(shí)數(shù)組
int[] left = new int[middle], right = new int[data.Length - middle], result = new int[data.Length];
//下面這句對(duì)性能有些影響，所以在上面有了改進(jìn)，直接用data.Length-middle初始化right數(shù)組
//if (data.Length % 2 != 0) right = new int[middle + 1];
//int i = 0, j = 0;
//foreach (int x in data)//開始排序
//{
// if (i < middle)//填充左數(shù)組
// {
// left[i] = x;
// i++;
// }
// else//填充右數(shù)組
// {
// right[j] = x;
// j++;
// }
//}
//上面的foreach被改成了for循環(huán)
//for (int i = 0; i < data.Length; i++)
//{
// if (i < middle)//用middle，不用left.Length
// {
// left[i] = data[i];
// }
// else
// {
// right[i - middle] = data[i]; //此處i-middle，讓我省掉定義一個(gè)j，性能有所提高
// }
//}
//經(jīng)調(diào)查,用Array.Copy的確比上面的for循環(huán)優(yōu)化很多
Array.Copy(data, 0, left, 0, middle);//拷貝左數(shù)組
Array.Copy(data, left.Length, right, 0, right.Length); //拷貝右數(shù)組
left = Sort(left);//遞歸左數(shù)組
right = Sort(right);//遞歸右數(shù)組
result = Merge(left, right);//開始排序
//this.Write(result);//輸出排序,測(cè)試用(lihua debug)
return result;
}
/// <summary>
/// 歸并排序之并:排序在這一步
/// </summary>
/// <param name="a">左數(shù)組</param>
/// <param name="b">右數(shù)組</param>
/// <returns>合并左右數(shù)組排序后返回</returns>
int[] Merge(int[] a, int[] b)
{
//定義結(jié)果數(shù)組，用來存儲(chǔ)最終結(jié)果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左數(shù)組中元素小于右數(shù)組中元素
{
result[k++] = a[i++];//將小的那個(gè)放到結(jié)果數(shù)組
}
else//左數(shù)組中元素大于右數(shù)組中元素
{
result[k++] = b[j++];//將小的那個(gè)放到結(jié)果數(shù)組
}
}
while (i < a.Length)//這里其實(shí)是還有左元素，但沒有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，無左元素
{
result[k++] = b[j++];
}
return result;//返回結(jié)果數(shù)組
}
2. C/C++實(shí)現(xiàn)如下
//歸并排序中之并
//Updated by zivsoft at 05/06/2009
int *Merge(int *a,int aLength,int *b,int bLength){
//合并結(jié)果指針
int *result;
//初始化結(jié)果指針
result=new int[aLength+bLength];
int i=0,j=0,k=0;
//定義左指針
a=new int[aLength];
//定義右指針
b=new int[bLength];
//元素排序,左右比較
while(i<aLength&&j<bLength){
if(a[i]<b[j]){//左元素小于右元素
result[k++]=a[i++];//將小的賦值到結(jié)果
}
else{//左元素大于右元素
result[k++]=b[j++];//將小的賦值到結(jié)果
}
}
while(i<aLength){//將最后一個(gè)元素賦值到結(jié)果
result[k++]=a[i++];
}
while(j<bLength){//將最后一個(gè)元素賦值到結(jié)果
result[k++]=b[j++];
}
return result;
}
//歸并排序中之歸拆分
//Updated by zivsoft at 05/06/2009
int *Split(int *data,int length){
int i=0,j=0,k=0;
int *left,*right,*result;
//取中間下標(biāo)
int middle=length/2;
left=new int[middle];
right=new int[middle];
//初始化有序結(jié)果數(shù)組
result=new int[length];
//如果數(shù)組只有一個(gè)元素,直接返回,無需排序
if(length<=1){
return data;
}
int rightLength=0;
//奇數(shù)個(gè)元素的話,重新分配右數(shù)組長(zhǎng)度
if(length%2!=0){
delete[] right;
rightLength=middle+1;
right=new int[rightLength];
}
//拆分?jǐn)?shù)組
for(k=0;k<length;k++){
if(i<middle){
left[i++]=data[k];
}
else{
right[j++]=data[k];
}
}
left=Split(left,i);//遞歸拆分左數(shù)組
right=Split(right,rightLength);//遞歸拆分右數(shù)組
result=Merge(left,i,right,rightLength);//排序并合并
//printarray(result,k); //輸出,供lihua(zorywa)側(cè)使用(zivsoft)
return result;
}
//Updated by zivsoft at 05/06/2009
int *Merge(int *a,int aLength,int *b,int bLength){
//合并結(jié)果指針
int *result;
//初始化結(jié)果指針
result=new int[aLength+bLength];
int i=0,j=0,k=0;
//定義左指針
a=new int[aLength];
//定義右指針
b=new int[bLength];
//元素排序,左右比較
while(i<aLength&&j<bLength){
if(a[i]<b[j]){//左元素小于右元素
result[k++]=a[i++];//將小的賦值到結(jié)果
}
else{//左元素大于右元素
result[k++]=b[j++];//將小的賦值到結(jié)果
}
}
while(i<aLength){//將最后一個(gè)元素賦值到結(jié)果
result[k++]=a[i++];
}
while(j<bLength){//將最后一個(gè)元素賦值到結(jié)果
result[k++]=b[j++];
}
return result;
}
//歸并排序中之歸拆分
//Updated by zivsoft at 05/06/2009
int *Split(int *data,int length){
int i=0,j=0,k=0;
int *left,*right,*result;
//取中間下標(biāo)
int middle=length/2;
left=new int[middle];
right=new int[middle];
//初始化有序結(jié)果數(shù)組
result=new int[length];
//如果數(shù)組只有一個(gè)元素,直接返回,無需排序
if(length<=1){
return data;
}
int rightLength=0;
//奇數(shù)個(gè)元素的話,重新分配右數(shù)組長(zhǎng)度
if(length%2!=0){
delete[] right;
rightLength=middle+1;
right=new int[rightLength];
}
//拆分?jǐn)?shù)組
for(k=0;k<length;k++){
if(i<middle){
left[i++]=data[k];
}
else{
right[j++]=data[k];
}
}
left=Split(left,i);//遞歸拆分左數(shù)組
right=Split(right,rightLength);//遞歸拆分右數(shù)組
result=Merge(left,i,right,rightLength);//排序并合并
//printarray(result,k); //輸出,供lihua(zorywa)側(cè)使用(zivsoft)
return result;
}
感言:
這個(gè)算法是我在XX的一個(gè)面試題,問如何高效率將兩個(gè)鏈表合并,并使之有序。很快想到歸并排序（Merge Sort)，想了想原理，把它實(shí)現(xiàn)了，不過現(xiàn)在又把它拿出來加了很多注釋，應(yīng)該沒什么大問題了吧，重要是理解算法的精髓，用什么實(shí)現(xiàn)應(yīng)該差不多，目前寫了C#和C/C++兩個(gè)版本，便于理解Merge Sort的原理，歡迎提建議，共同提高。 :-)
本文鏈接:http://www.rzrgm.cn/architect/archive/2009/05/06/1450489.html
關(guān)于作者:http://www.zivsoft.com/
posted on 2009-05-06 10:59 智艾悅 閱讀(5218) 評(píng)論(17) 收藏 舉報(bào)
浙公網(wǎng)安備 33010602011771號(hào)