归并排序算法实现

本文概述

• 复杂
• 例
• 算法
• C程序
• Java程序
• C＃程序

合并排序是遵循分而治之的算法。考虑一个n个元素的数组A。该算法分3个步骤处理元素。

1. 如果A包含0或1个元素, 则它已经被排序, 否则, 将A分为元素数量相等的两个子数组。
2. 征服意味着使用合并排序对两个子数组进行递归排序。
3. 合并子数组以形成单个最终排序的数组, 以保持数组的顺序。

合并排序的主要思想是, 简短列表的排序时间更少。

复杂

例

考虑以下由7个元素组成的数组。使用合并排序对数组进行排序。

A = {10, 5, 2, 23, 45, 21, 7}

算法

• 步骤1：[INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0
• 步骤2：如果ARR [I] <ARR [J] SET TEMP [INDEX] = ARR [I] SET I = I + 1 ELSE SET TEMP [INDEX], 则重复（I <= MID）和（J <= END） = ARR [J] SET J = J + 1 [IF结束] SET INDEX = INDEX + 1 [LOOP结束]步骤3：[复制右侧子阵列的其余元素（如果有）] IF I> MID J <=结束SET TEMP [INDEX] = ARR [J] SET INDEX = INDEX + 1, SET J = J +1 [END OF LOOP] [复制左子数组的剩余元素, 如果有的话] ELSE <= MID SET TEMP [INDEX] = ARR [I] SET INDEX = INDEX + 1, SET I = I + 1 [LOOP结束] [IF结束]
• 步骤4：[将TEMP的内容复制回ARR] SET K = 0
• 步骤5：在K <INDEX SET ARR [K] = TEMP [K] SET K = K + 1 [LOOP LOOP]时重复
• 步骤6：退出

MERGE_SORT（ARR, BEG, END）

• 步骤1：如果BEG <END SET MID =（BEG + END）/ 2呼叫MERGE_SORT（ARR, BEG, MID）呼叫MERGE_SORT（ARR, MID + 1, END）合并（ARR, BEG, MID, END）[END OF如果]
• 步骤2：结束

C程序

#include<stdio.h>
void mergeSort(int[], int, int);
void merge(int[], int, int, int);
void main ()
{
	int a[10]= {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
	int i;
	mergeSort(a, 0, 9);
	printf("printing the sorted elements");
	for(i=0;i<10;i++)
	{
		printf("\n%d\n", a[i]);
	}
	
}
void mergeSort(int a[], int beg, int end)
{
	int mid;
	if(beg<end)
	{
		mid = (beg+end)/2;
		mergeSort(a, beg, mid);
		mergeSort(a, mid+1, end);
		merge(a, beg, mid, end);
	}
}
void merge(int a[], int beg, int mid, int end)
{
	int i=beg, j=mid+1, k, index = beg;
	int temp[10];
	while(i<=mid && j<=end)
	{
		if(a[i]<a[j])
		{
			temp[index] = a[i];
			i = i+1;
		}
		else 
		{
			temp[index] = a[j];
			j = j+1; 
		}
		index++;
	}
	if(i>mid)
	{
		while(j<=end)
		{
			temp[index] = a[j];
			index++;
			j++;
		}
	}
	else 
	{
		while(i<=mid)
		{
			temp[index] = a[i];
			index++;
			i++;
		}
	}
	k = beg;
	while(k<index)
	{
		a[k]=temp[k];
		k++;
	}
}

输出：

printing the sorted elements 

7
9
10
12
23
23
34
44
78
101

Java程序

public class MyMergeSort
{
void merge(int arr[], int beg, int mid, int end)
{

int l = mid - beg + 1;
int r = end - mid;

intLeftArray[] = new int [l];
intRightArray[] = new int [r];

for (int i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];

for (int j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];


int i = 0, j = 0;
int k = beg;
while (i<l&&j<r)
{
if (LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i<l)
{
arr[k] = LeftArray[i];
i++;
k++;
}

while (j<r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}

void sort(int arr[], int beg, int end)
{
if (beg<end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[])
{
intarr[] = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23};
MyMergeSort ob = new MyMergeSort();
ob.sort(arr, 0, arr.length-1);

System.out.println("\nSorted array");
for(int i =0; i<arr.length;i++)
{
	System.out.println(arr[i]+"");
}
}
}

输出：

Sorted array 
23
23
23
34
45
65
67
89
90
101

C＃程序

using System;
public class MyMergeSort
{
void merge(int[] arr, int beg, int mid, int end)
{

int l = mid - beg + 1;
int r = end - mid;
		int i, j;

int[] LeftArray = new int [l];
int[] RightArray = new int [r];

for (i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];

for (j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];


i = 0; j = 0;
int k = beg;
while (i < l && j < r)
{
if (LeftArray[i] <= RightArray[j])
{
arr[k] = LeftArray[i];
i++;
}
else
{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i < l)
{
arr[k] = LeftArray[i];
i++;
k++;
}

while (j < r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}

void sort(int[] arr, int beg, int end)
{
if (beg < end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void Main()
{
int[] arr = {90, 23, 101, 45, 65, 23, 67, 89, 34, 23};
MyMergeSort ob = new MyMergeSort();
ob.sort(arr, 0, 9);

Console.WriteLine("\nSorted array");
for(int i =0; i<10;i++)
{
	Console.WriteLine(arr[i]+"");
}
}
}

输出：

Sorted array 
23
23
23
34
45
65
67
89
90
101