Biegral Blog

   希尔排序是对直接插入排列的改进，又叫缩小增量排序，就是将gap不断缩小的插入排序，代码如下:

#include<iostream>
using namespace std;

void shellSort(int a[], int n)
{
	int i, j, pivotKey, gap;
	for(gap = n/2; gap > 0; gap--)
	{
		for(i = gap; i < n; i++)
		{
			pivotKey = a[i];
			for(j = i - gap; j >= 0 && a[j] > pivotKey; j -= gap)
				a[j + gap] = a[j];
			a[j + gap] = pivotKey; //恢复
		}
	}
}

int main()
{
	int a[] = {4, 5, 1, 3, 2, 0, -3 ,-20, 100, 50};
	shellSort(a, 10);
	int i;
	for(i = 0; i < 10; i++)
		cout << a[i] << " ";
	cout << endl;
    return 0;
}