mergesortimp.java

用JAVA实现排序等简单算法的演示

package algorithmImp;

public class MergeSortImp extends SortAlgorithmImp {
	protected int[] mergingData = null;
	
	public void sorting() {
		mergingData = new int[data.length];
		mergeSort(0, data.length);
	}
	
	/**
	 * 将 startIndex（包括） 到 midIndex(不包括）处的（已排序）元素和midIndex(包括）到endIndex(不包括）处的（已
	 * 排序）元素合并到 startIndex 到 endIndex。合并的中间结果先放在 mergingData，然后拷贝回 data。
	 */
	protected void merge(int startIndex, int midIndex, int endIndex) {
		int firstIndex = startIndex;
		int secondIndex = midIndex;
		int resultIndex = startIndex;
		
		while (firstIndex < midIndex && secondIndex < endIndex) {
			if (!compare(firstIndex, secondIndex)) {
				// 如果 firstIndex 处的元素小于等于 secondIndex 处的元素则放 firstIndex 到 resultIndex 处
				copyData(resultIndex, firstIndex);
				resultIndex = resultIndex + 1;
				firstIndex = firstIndex + 1;
			} else {
				copyData(resultIndex, secondIndex);
				resultIndex = resultIndex + 1;
				secondIndex = secondIndex + 1;
			}
		}
		// 合并剩下的元素
		while (firstIndex < midIndex) {
			copyData(resultIndex, firstIndex);
			resultIndex = resultIndex + 1;
			firstIndex = firstIndex + 1;
		}
		while (secondIndex < endIndex) {
			copyData(resultIndex, secondIndex);
			resultIndex = resultIndex + 1;
			secondIndex = secondIndex + 1;
		}
		// 将合并后的数据拷贝回 data。注意我们这里没有继续利用mergingData进行下一轮合并，而总是针对
		// data 进行合并，只是将 mergingData 作为临时存储使用，当然这降低了排序效率
		copyMergedData(startIndex, endIndex);
	}
	
	protected void mergeSort(int startIndex, int endIndex){
		int midIndex = (startIndex+endIndex)/2;

		// 下面的 if 语句中的条件是保证当只有一个元素时，无需再递归
		if (startIndex < midIndex-1) mergeSort(startIndex, midIndex);
		if (midIndex < endIndex-1) mergeSort(midIndex, endIndex);
		merge(startIndex, midIndex, endIndex);
	}
	
	/**
	 * 将 startIndex 到 endIndex-1 处的元素从 mergingData 拷贝回 data，将这种拷贝抽取为方法使得可演示
	 * 这种拷贝过程。
	 */
	private void copyMergedData(int startIndex, int endIndex) {
		for (int index = startIndex; index < endIndex; index++) data[index] = mergingData[index];
	}

	/**
	 * 将 data 的 dataIndex 处的数据拷贝到 mergingData 的 mergingIndex 处。将这种拷贝抽取为方法使得
	 * 可演示这种拷贝过程。
	 */
	private void copyData(int mergingIndex, int dataIndex) {
		mergingData[mergingIndex] = data[dataIndex];
	}

}