Java版希尔排序(缩小增量排序)[不稳定]

Answer 1

复杂度 平均 O(n^1.3) 最好O(n) 最差O(n^s)[1

内循环通过模拟并行的方式完成分组的内部直接插入排序，而不是一个一个分组分组的排，在10w的随机数据20w的随机数据均表现优异。

public void shellSort(int[] a) {
	if (null == a || a.length < 2) {
		return;
	}
	for (int d = a.length/2; d > 0; d/=2) {
		// 从1B开始先和1A比较 然后2A与2B...然后再1C向前与同组的比较
		for (int i = d; i < a.length; i++) {
		// 内部直接插入
			int temp = a[i];
			int j = i - d;
			while (j >=0 && temp < a[j]) {
				a[j+d] = a[j];
				j -= d;
			}
			a[j+d] = temp;
		}
	}
}