插入排序

插入排序分三种： 直接插入排序、 折半插入排序 以及 希尔排序

× 直接插入排序

/**
 * 直接插入排序， 和打扑克插牌有点类似
 */
private void directInsertSort(int[] source) {
	for (int i = 0; i < source.length; i++) {
		for (int j = 0; j <= i; j++) {
			if (source[i] < source[j]) {
				source[i] = source[i] ^ source[j];
				source[j] = source[i] ^ source[j];
				source[i] = source[i] ^ source[j];
			}
		}
	}
}

* 折半插入排序

/**
 * 折半插入排序， 就是利用二分查找的方式来查找元素的插入位置
 */
private void binaryInsertSort(int[] soruce) {
	for (int i = 0; i < source.length; i++) {
		int currentValue = source[i];
		// 非递归查找出目标index
		int low = 0;
		int high = i - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (source[mid] < source[i])
				low = mid + 1;
			else
				high = mid - 1;
		}
		// 向后移目标index到当前index之间的元素
		for (int j = i; j > low; j--)
			source[j] = source[j - 1];
		// 将当前值插入到目标index位置
		source[low] = currentValue;
	}
}

* 希尔排序

/**
 * 希尔排序思想就是先对子序列进行直接插入排序, 使得整个序列"基本有序", 一次减少比较和移动的次数. 最后对整个序列进行一次直接插入排序就可以了.
 * 
 * 其关键之处就在于对步长的选择
 */
private static void shellSort(int[] source) {
	int step = 1;
	// 目前貌似都一“Kunth序列”作为shell排序的步长
	while (step <= source.length / 3)
		step = step * 3 + 1;
	while (step > 0) {
		for (int i = step; i < source.length; i++) {
			int pos = i;
			int currentValue = source[i];
			// 将整个子序列排序， 当step = 1时就成了直接快速排序。 事实上， 对于每一个当前元素， 其所在的子序列中index比它小的所有元素已经是有序的了。
			while (pos >= step && currentValue < source[pos - step]) {
				source[pos] = source[pos - step];
				pos -= step;
			}
			source[pos] = currentValue;
		}

		// 更新步长
		step = (step - 1) / 3;
	}
}