希尔排序

void ShellSort(int A[], int n) {
	int d, i, j;
	for(d = n / 2; d >= 1; d = d / 2) {
		for(i = d + 1; i <= n; ++i) {
			if(A[i] < A[i - d]) {
				A[0] = A[i];
				for(j = i - d; j > 0 && A[0] < A[j]; j -= d) {
					A[j + d] = A[j];
				}
				A[j + d] = A[0];
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1. 空间复杂度：

2. 最坏时间复杂度：O(n²)
   平均时间复杂度：O(n^1.3) 大概

3. 算法稳定性：不稳定

4. 手算过程（重要）