插入排序与归并排序

2019年9月22日

---

​ 近几天刚看算法导论，里面的算法复杂度计算推导看起来有点费力，很多概念都不是很理解，数学推导不知道在说个啥。。。就想着先把算法都学了再说，以后理解再慢慢说。下面是插入排序和归并排序。

​ 插入排序；运用增量的思想，排好子序列A[1…k]后将A[k+1]排序插入其中构成新序列。插排原理比较好理解，导论里用打牌时排序抽到的手牌举例就很好理解。其时间复杂度为O(N^2),代码如下：

package sort;
public class InsertSort {
	private static void go(int[] list, int order) {
		for(int i = 1; i < list.length; i++) {
			int key = list[i];
			int j = i-1;
			if(order > 0) {
				while(j >= 0 && list[j] > key) {
					list[j+1] = list[j--];
				}
			}
			else {
				while(j >= 0 && list[j] < key) {
					list[j+1] = list[j--];
				}
			}
			list[j+1] = key;
		}
	}
	
	public static void apply(int[] list, int order) {
		go(list, order);
	}
}

​ 归并排序；运用分治的思想，将序列分为数个子序列每个序列内排序后再组合成较大的序列，以此类推。。其平均情况下的时间复杂度为O(NlogN)；导论里见到的用递归实现，基本可以概括为三步：①将手中的序列分为两半；②让分成的这两半进行排序（这里递归操作）；③将被排序后的两端序列组合在一起；

​ 我个人编写中的体验是，和冒泡、插排不同，归并很难在原序列上进行操作（仅凭交换操作），网上查到大多人的实现都是另外申请空间造一个新数组往里面填，再加上使用递归，所需要的空间就会很大（它的空间复杂度貌似O(NlogN)?）数据量过大的话甚至造成栈溢出。因此基本只是用在外部排序，还有人将递归改成迭代进行优化，这也是很好的。

​ 下面是我自己实现的代码，尽管很多地方都写的不够好：

package sort;
public class MergeSort {
	//order为排序方向，0为反序
	private static int[] go(int[] array, int left, int right, int order) {
		int mid = (right + left)/2;
		int length = right - left + 1;
		int[] result = new int[length];
		if(length <= 1) {
			result[0] = array[left];
			return result;
		}
		int[] result1 = go(array, left, mid, order);
		int[] result2 = go(array, mid + 1, right, order);
		sort(result1, result2, result, mid - left + 1, right - mid, order);
		return result;	
	}
	
	public static void apply(int[] list, int order) {
		int[] anotherlist = go(list, 0, list.length - 1, order);
		for(int i = 0; i < list.length; i++) {
			list[i] = anotherlist[i];
		}
	}
	
	private static void sort(int[] result1, int[] result2, int[] result, int left, int right, int order) {
		int i = 0,
			j = 0,
			k = 0;
		while(i < left && j < right) {
			if(result1[i] < result2[j]) {
				if(order > 0) {
					result[k++] = result1[i++];
				}
				else {
					result[k++] = result2[j++];
				}
			}
			else {
				if(order > 0) {
					result[k++] = result2[j++];
				}
				else {
					result[k++] = result1[i++];
				}
			}
		}
		while(j < right) {
			result[k++] = result2[j++];
		}
		while(i < left) {
			result[k++] = result1[i++];
		}
	}
}