Posted on 2011-09-22 00:34
kalvinyZhang 阅读(133)
评论(0) 编辑 收藏 引用 所属分类:
OJ
这个题，各种排序练习不解释呀，很好的练习基础排序的题目，现在用了插入和shell排序，可以继续快点呀，先贴着吧
#include <stdio.h>#define MAX 1000
int main()
{
int n, m, i, j, tmp;
int s[MAX], t[MAX];
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (i = 0; i < m; i++)
scanf("%d", &s[i]);
for (i = m-1; i >= 1; i--) {
t[i] = s[i] - s[i-1];
}
t[0] = s[0];
/**
insert sort
for (i = 1; i < m; i++) {
tmp = t[i];
for (j = i; j > 0 && t[j-1] > tmp; j--)
t[j] = t[j-1];
t[j] = tmp;
}
**/
//shellsort
int gap;
for (gap = m / 2; gap > 0; gap /= 2) {
for (i = gap; i < m; i++) {
tmp = t[i];
for (j = i; j >= gap; j -= gap)
if (tmp < t[j - gap])
t[j] = t[j - gap];
else
break;
t[j] = tmp;
}
}
for (i = 0; i < m; i++)
printf("%d ", t[i]);
printf("\n");
}
return 0;
}