用c语言编写一个希尔排序程序，新手，最好能给注释下！谢谢

Question

如题所述

Answer 1

网友wang1992092对希尔排序的理解有些错误，希尔排序对每个子序列进行的是直接插入排序，而不是如他所给出的选择排序。你可以先百度一下希尔排序的定义。我这里给一个C源代码，你可以试试。直接插入排序的思路是：将待排表分成两部分，一部分是已有序部分L，另一部分是待排序部分R。L初始化为只含第一个元素的表，因L现在只含一个元素，所以是有序的。然后每次从R中取出最前面的元素到tmp(相当于出队到tmp中)，然后在L中从后向前搜索插入位置，边搜索边向后移动比tmp大的元素，找到了插入位置后就将tmp插入到L中。直到R部分为空时结束。
typedef int datatype;
void InsertSort(datatype a[], int left, int right, int gap)
/*对数组a中起始下标为left，结束下标为right，步长为gap的子序列进行直接插入排序，当gap等于1时就是通常的插入排序了*/
{
int tmp, i, j;
for(i = left + gap; i <= right; i += gap){
for(tmp = a[i], j = i - gap; j >= left && a[j] > tmp; j -= gap)
a[j + gap] = a[j];
a[j + gap] = tmp;
}
}

void ShellSort(datatype a[], int left, int right)
{
int gap = (right - left + 1) / 2, i;/*步长gap初始化为n/2取下整*/
while(gap > 0)
{
for(i = left; i < gap; i++) /*对每个子序列进行直接插入排序*/
InsertSort(a, i, right, gap);
gap = gap / 2; /*将步长缩小为原来的一半并取下整*/
}
}追问

你好，还能问你一道c语言的题么？用c语言编写一道二叉树先序遍历的程序，用递归的方法，我还没学过数据结构，给点儿解释。谢谢。。。

追答

设结点结构为Node(data, *child, *child)，则对根为root的二叉树进行前序遍历的过程为：
（1）如果root为空，则遍历结束；
（2）访问根结点root；（访问时一般是将结点中的数据输出）
（3）对root->lchild为根的左子树采用同样的前序遍历方法进行遍历；
（4）对root->rchild为根的右子树采用同样的前序遍历方法进行遍历；
程序代码可如下：
void PreOrder(Node *root)
{
if(root == NULL) return;
printf("%d\t", root->data); /*访问根结点*/
PreOrder(root->lchild); /*前序遍历左子树
PreOrder(root->rchild); /*前序遍历右子树*/
}

Answer 2

当初学习算法的时候写的希尔排序函数，仅供参考。
动态增长容易用数组代替也可以

void shellsort(vector<student>& svec)//希尔排序
{
int k = 5;
int min = 0;
for (int i = 0; i < LEN; i+=5)//5为步长
{
if (svec[i].id < svec[min].id)
min = i;
swap(svec[min], svec[i]);
}
k = 3;
for (int i = 0; i < LEN; i+=3)//3为步长
{
if (svec[i].id < svec[min].id)
min = i;
swap(svec[min], svec[i]);
}
selectsort(svec);//做一次完整的选择排序，也就是步长为1
}