希尔排序（C++）

#include		//希尔排序 
using namespace std;

void exch(int a[], int i, int j) {	//交换数组中的两个数
	int temp;
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

int main() {
	int a[100000] = {};
	int N;
	int i, j;
	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> a[i];
	}
	int h = 1;
	while (h < N / 3) {
		h = 3 * h + 1;
	}
	while (h >= 1) {
		for (i = h; i < N; i++) {
			for (j = i; j >= h && a[j] < a[j - h]; j -= h) {
				exch(a, j, j - h);
			}
		}
		h = h / 3;
	}

	for (i = 0; i < N; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

测试结果：