1373 - 算法10-4,10-5：希尔排序

10
2 8 4 6 1 10 7 3 5 9

1 2 3 4 5 6 7 8 9 10 

Hint

在本题中，需要按照题目描述中的算法完成希尔排序的算法。
希尔排序的时间复杂度分析是一个复杂的问题，因为其时间与所取的“增量序列”相关。目前为止尚未有人求得一种最好的增量序列。增量序列可以有多种不同的取法，但是需要注意的是，在选取增量序列时务必使序列中的值没有除1以外的公因子，且最后一个增量值必须等于1。
与直接插入排序相比，通过选择合适的增量序列，希尔排序算法能够使排序的效率得到部分的提高，但是由于其形式的复杂性和增量序列选择并没有定论，所以在实际应用中希尔排序是非常少见的。

Solution C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int s[10000],n,i;
int cmp(const void *a,const void *b)
{
     return(*(int *)a-*(int *)b);//ÉýÐò£»b-a½µÐò
}
int main()
{
    scanf("%d",&n);
    for(i=0;i<n;i++)
	    scanf("%d",&s[i]);
    qsort(s,n,sizeof(s[0]),cmp);
    for(i=0;i<n;i++)
	    printf("%d ",s[i]);
  printf("\n");
    return 0;
}

Solution C++

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
int val[MAXN];
int n;
void ShellInsert(int dk) {
	int current;
	for (int i = dk;i < n;i++) {
		if (val[i] < val[i - dk]) {
			current = val[i];
			int j;
			for (j = i - dk;j >= 0 && current < val[j];j -= dk)
				val[j + dk] = val[j];
			val[j + dk] = current;
		}
	}
}
void ShellSort() {
	int current, t = 4;
	int dlta[] = {7, 5, 3, 1};
	for (int i = 0;i < t;i++) {
		ShellInsert(dlta[i]);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0;i < n;i++) {
		scanf("%d", &val[i]);
	}
	ShellSort();
	for (int i = 0;i < n;i++) {
		printf("%d ", val[i]);
	}
	puts("");
	return 0;
}