希尔排序

• 改进的插入排序算法

• 稳定

算法思想

第一种

先分组,每组头一个比较大小进行交换
逐渐缩小组大小,继续交换做插入排序

public static void main(String[] args) {
	// int nums[] = {49, 38, 65, 97, 76, 13, 27, 49, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
	// int nums[] = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
	// [1, 6, 2, 3, 5, 12, 8, 4, 9, 13, 11, 7, 10, 15, 14]
	int nums[] = {9, 2, 1, 6, 5, 8, 7, 4, 3};
	sort(nums, 3);
	System.out.println(Arrays.toString(nums));
}

private static void sort(int[] nums, int h) {
	for (int part = h; part > 0; part /= 2) {
		for (int i = part; i < nums.length; i++) {
			for (int j = i; j > part - 1; j = j - part) {
				if (nums[j] < nums[j - part]) {
					swap(nums, j, j - part);
				}
			}
		}
	}
}

public static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

第二种

• 第一种方法存在问题,如何选定初始组的大小,以及如何设定一个可靠有效合理的组缩小测略

Knuth序列

h=1  
h=3*h+1

private static void sort(int[] nums) {
	int h = 1;
	while (h <= nums.length / 3) {
		h = h * 3 + 1;
	}
	for (int part = h; part > 0; part = (part - 1) / 3) {
		for (int i = part; i < nums.length; i++) {
			for (int j = i; j > part - 1; j = j - part) {
				if (nums[j] < nums[j - part]) {
					swap(nums, j, j - part);
				}
			}
		}
	}
}

时空复杂度

时间复杂度

O(n^1.3)

空间复杂度

O(1)