insert_sort

//含"无用比较"的插入排序
void insertion_sort(int a[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (a[i] < a[j]) {
				int tmp = a[j];
				a[j] = a[i];
				a[i] = tmp;
			}
		}
	}
}

//“优化”比较过程的插入排序
void insertion_sort2(int a[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (a[i] < a[j]) {
				int tmp = a[i];
				//整段移动，这里的k每次循环需要和j比较...
				for (int k = i; k > j; --k) {
					a[k] = a[k - 1];
				}
				a[j] = tmp;
				break;
			}
		}
	}
}
//结论：整段移动并没有减少“比较”