#include <cstdio>
using namespace std;
void shell_sort(int dataList[], int count);
int main() {
// your code goes here
int arr[10] = { 0, 2, 9, 8, 3, 1, 7, 5, 6, 4 };
shell_sort(arr, 10);
for(int i = 0; i < 10; i++) printf("%d ", arr[i]);
return 0;
}
void shell_sort(int dataList[], int count)
{
int k = 3, gap = count / k;
while (gap > 0)
{
for (int i = gap; i < count; i++)
{
int tmp = dataList[i];
int j = i;
while (j >= gap && dataList[j - gap] > tmp)
{
dataList[j] = dataList[j - gap];
j -= gap;
}
dataList[j] = tmp;
}
gap /= k;
}
}
I2luY2x1ZGUgPGNzdGRpbz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgc2hlbGxfc29ydChpbnQgZGF0YUxpc3RbXSwgaW50IGNvdW50KTsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IGFyclsxMF0gPSB7IDAsIDIsIDksIDgsIDMsIDEsIDcsIDUsIDYsIDQgfTsKCXNoZWxsX3NvcnQoYXJyLCAxMCk7Cglmb3IoaW50IGkgPSAwOyBpIDwgMTA7IGkrKykgcHJpbnRmKCIlZCAiLCBhcnJbaV0pOwoJcmV0dXJuIDA7Cn0KCnZvaWQgc2hlbGxfc29ydChpbnQgZGF0YUxpc3RbXSwgaW50IGNvdW50KQogICAgICAgIHsKICAgICAgICAgICAgaW50IGsgPSAzLCBnYXAgPSBjb3VudCAvIGs7CiAgICAgICAgICAgIHdoaWxlIChnYXAgPiAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gZ2FwOyBpIDwgY291bnQ7IGkrKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpbnQgdG1wID0gZGF0YUxpc3RbaV07CiAgICAgICAgICAgICAgICAgICAgaW50IGogPSBpOwogICAgICAgICAgICAgICAgICAgIHdoaWxlIChqID49IGdhcCAmJiBkYXRhTGlzdFtqIC0gZ2FwXSA+IHRtcCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGRhdGFMaXN0W2pdID0gZGF0YUxpc3RbaiAtIGdhcF07CiAgICAgICAgICAgICAgICAgICAgICAgIGogLT0gZ2FwOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBkYXRhTGlzdFtqXSA9IHRtcDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGdhcCAvPSBrOwogICAgICAgICAgICB9CiAgICAgICAgfQ==