java实现归并排序

?

归并排序

?

?????? 归并排序，指的是将两个已经排序的序列合并成一个序列的操作。

?

归并操作的过程如下：

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

	/**
	 * 归并排序
	 * 
	 * @param ts
	 */
	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void mergeSort(T[] ts) {

		// 辅助空间
		T[] tempArray = (T[]) new Comparable[ts.length];

		mergeSort(ts, tempArray, 0, ts.length - 1);
	}

	/**
	 * 递归
	 */
	private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) {

		if (left < right) {

			int center = (left + right) / 2;

			mergeSort(ts, tempArray, left, center);

			mergeSort(ts, tempArray, center + 1, right);

			// 左右合并
			merge(ts, tempArray, left, center + 1, right);

		}

	}

	/**
	 * 合并
	 */
	private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos - 1;
		int temPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		while (leftPos <= leftEnd && rightPos <= rightEnd)
			//比较放到辅助空间
			if (ts[leftPos].compareTo(ts[rightPos]) <= 0)
				tempArray[temPos++] = ts[leftPos++];
			else
				tempArray[temPos++] = ts[rightPos++];

		while (leftPos <= leftEnd)
			tempArray[temPos++] = ts[leftPos++];

		while (rightPos <= rightEnd)
			tempArray[temPos++] = ts[rightPos++];

		//考回原数组,此处最好用System.arraycopy优化
		for (int i = 0; i < numElements; i++, rightEnd--)
			ts[rightEnd] = tempArray[rightEnd];
	}

?

?复杂度：O(n log n)

?????? 比较操作的次数介于和。 赋值操作的次数是。

???????? 归并算法的空间复杂度为：Θ(n)

?

?稳定性：稳定

?

扩展：

?????? 在java中，当执行一次泛型排序时，进行一次元比较可能是昂贵的，但是移动元素则是省时间的。归并排序使用所有的流行的排序算法中最少的比较次数，因此是使用java的通用排序算中的上好的选择。

????