排序算法——归并排序

基本思想

把一个序列切分成左右两个子序列，然后分别再切分左右两个子序列，一次切分下去，直到每个序列不能再切分为止，也就是只剩一个元素。这是一个递归的过程。然后将每个子序列排序合并，最后合并成一个完整的有序的序列。

图解如下：

归并过程如下动态图：

代码实现

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
		  int[] data = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
		  mergeSort(data,0,data.length - 1);
		  System.out.println("归并排序结果：" + Arrays.toString(data));
    }
	
	/**
	 * 归并排序
	 * @param data 数组
	 * @param left 数组起始位置
	 * @param right 数组结束位置
	 */
	public static void mergeSort(int[] data,int left,int right) {
		if(left < right) {
			// 将数组从中间切分成左右两个子数组
			int mid = (left + right) / 2;
			// 递归切分左边子数组
			mergeSort(data, left, mid);
			// 递归切分右边子数组
			mergeSort(data, mid+1, right);
			// 开始将切分的子数组排序合并
			merge(data, left, mid, right);
		}
	}
	
	/**
	 * 对子数组进行合并排序
	 * @param data 数组
	 * @param left 数组起始位置
	 * @param mid 数组中间位置
	 * @param right 数组结束位置
	 */
	private static void merge(int[] data, int left, int mid, int right) {
		int[] tmp = new int[data.length];
		// 左边子数组开始位置
		int leftPointer = left;
		// 右边子数组开始位置
		int rightPointer = mid + 1;
		// 临时数组的游标指针，起始位置为left
		int loc = left;
		while(leftPointer <= mid && rightPointer <= right) {
			if(data[leftPointer] < data[rightPointer]) {
				// 如果左边的数小于右边的数，就将左边小的数放入到临时数组中
				// 并且将loc++,leftPointer++
				tmp[loc++] = data[leftPointer++];
			} else {
				// 如果左边的数大于等于右边的数，就将右边的数放入到临时数组中
				// 并且将loc++,rightPointer++
				tmp[loc++] = data[rightPointer++];
			}
		}
		// 将左边没有放入临时数组的数放入到临时数组中
		while(leftPointer <= mid) {
			tmp[loc++] = data[leftPointer++];
		}
		// 将右边没有放入临时数组的数放入到临时数组中
		while(rightPointer <= right) {
			tmp[loc++] = data[rightPointer++];
		}
		// 将临时数组中排好序的元素放到data中
		for(int i = left; i <= right; i++) {
			data[i] = tmp[i];
		}
	}
	
}

复杂度

• 时间复杂度：O(nLogn)
• 空间复杂度：T(N) ，归并排序过程中创建了一个与原来数组一样大小的临时数组。