排序算法第三篇——归并排序

算法描述：

归并（Merge）排序是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

对一个数组进行归并排序主要分为以下三步：

1、分解。将一个数组分为两个个数组。

2.、治之。对分好的两个数组，分别用归并排序算法进行排序。

3、归并。将两个数组归并。

Java源代码：

<span style="font-size: 18px;">package ljp.sort.merge;

public class MergeSortDemo01 {
	private int[] list;
	//构造函数，初始化数组
	public MergeSortDemo01() {
		list = new int[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = (int) (Math.random() * 1000);
		}
	}
	//排序函数
	public void sort(int begin, int end) {
		int d = (begin + end) / 2;
		if (begin != end) {
			sort(begin, d);
			sort(d + 1, end);
			merge(begin, d + 1, end);
		}
	}
	//归并函数
	private void merge(int start, int mid, int end) {
		System.out.println("合并 第" + (start+1) + "到" + mid + "之间的元素 和  第" + (mid+1)
				+ "到" + (end+1)+"之间的元素");
		int len = end - start + 1;
		int[] temp = new int[len];
		int index = 0;
		int i = start;
		int j = mid;
		while (i < mid && j <= end) {
			if (list[i] > list[j]) {
				//System.out.println("第" + i + "个元素 大于 第" + j + "个元素");
				temp[index] = list[j];
				index++;
				j++;
			} else {
				//System.out.println("第" + i + "个元素 小于 第" + j + "个元素");
				temp[index] = list[i];
				index++;
				i++;
			}
		}
		if (i < mid) {
			while (index < len) {
				temp[index] = list[i];
				i++;
				index++;
			}
		}
		if (j <= end) {
			while (index < len) {
				temp[index] = list[j];
				j++;
				index++;
			}
		}
		for (int k = start; k <= end; k++) {
			list[k] = temp[k - start];
		}
		display();
	}

	public int getLength(){
		return this.list.length;
	}
	
	public void display() {
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		MergeSortDemo01 mergesort = new MergeSortDemo01();
		System.out.println("排序前：");
		mergesort.display();
		mergesort.sort(0, mergesort.getLength()-1);
	}

}</span>

运行结果：

排序前：
824 692 469 255 518 492 177 403 325 350
合并 第1到1之间的元素 和 第2到2之间的元素
692 824 469 255 518 492 177 403 325 350
合并 第1到2之间的元素 和 第3到3之间的元素
469 692 824 255 518 492 177 403 325 350
合并 第4到4之间的元素 和 第5到5之间的元素
469 692 824 255 518 492 177 403 325 350
合并 第1到3之间的元素 和 第4到5之间的元素
255 469 518 692 824 492 177 403 325 350
合并 第6到6之间的元素 和 第7到7之间的元素
255 469 518 692 824 177 492 403 325 350
合并 第6到7之间的元素 和 第8到8之间的元素
255 469 518 692 824 177 403 492 325 350
合并 第9到9之间的元素 和 第10到10之间的元素
255 469 518 692 824 177 403 492 325 350
合并 第6到8之间的元素 和 第9到10之间的元素
255 469 518 692 824 177 325 350 403 492
合并 第1到5之间的元素 和 第6到10之间的元素
177 255 325 350 403 469 492 518 692 824

该算法的时间复杂度为O(nlog2n)，算法是稳定的。