数据结构各种排序算法的课程设计实验报告(c语言版)
3.3 希尔排序
⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。 ⑵程序实现及核心代码的注释：
for(k = 0; k < 10 ; k++) { }
m = 10 - k;
for( i = m ; i < r.length; i ++ )
if(r.base[i] < r.base[i - m]) { }
temp = r.base[i]; //保存待插记录 for(j = i - m ; j >= 0 && temp < r.base[j]; j -= m)
r.base[ j + m ] = r.base[j]; //记录后移，查找插入位置
r.base[ j + m ] = temp; //插入
3.4简单选择排序
⑴算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。 ⑵程序实现及核心代码的注释：
for ( i = 0 ; i < r.length ; i++ )
{ //i为排好序的数的下标，依次往后存放排
//好序的数
temp=r.base[i]; //将待放入排好序的数的下标的数保存 for( j = i,m = j +1 ; m < r.length ; m++) //找出未排序的数中最小的数的循环；
if(r.base[j] > r.base[m])
j = m;
}
r.base[i] = r.base[j]; //把下标为j的数与i数互换； r.base[j] = temp;
3.5堆排序
⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉
6 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。
⑵程序实现及核心代码的注释： void dp(FILE *fp) {
for(i = r.length / 2;i >= 1 ; --i) //把r.base[1...r.length]建成大顶堆
HeapAdjust(r.base,i,r.length);
for(i = r.length ;i >= 2 ; --i)
{
temp = r.base[1]; r.base[1] = r.base[i];
}
r.base[i] = temp;
HeapAdjust(r.base,1,i-1); //将r.base[1...i-1]重新调整为大顶堆
void HeapAdjust(char *r,int k,int m) {
i=k; x=r[i]; j=2*i; //沿key 较大的孩子节点向下筛选 while(j<=m) //j为key较大的记录的下标 { }
r[i] = x; //把字符x插入到该位置，元素插入实现 if( (j
j++;
if(x>r[j])
{ //插入字符比当前的大，交换 }
else //否则比较停止。
j = m + 1; r[i] =r[j]; i = j; j *= 2;
}
3.6归并排序
⑴算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2
7 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。 ⑵程序实现及核心代码的注释：
void merge(SqList6 r,int h ,int m ,int w ,SqList6 t)
{ //对相邻两组数据进行组合排序；
int i,j,k; i = h ;
j = m + 1; //j为合并的第二组元素的第一个数位置 k =h-1； while((i <= m)&&(j <= w))
{ k++;
if(r.base[i] <= r.base[j]) t.base[k] = r.base[i++];
else
t.base[k] = r.base[j++]; } if(i > m)
while(j <= w) t.base[++k]=r.base[j++];
else while(i <= m) t.base[++k]=r.base[i++]; }
void tgb(int s,int n,SqList6 r,SqList6 t)
{ int i=1; while(i<=(n-2*s+1))
{
merge(r,i,i+s-1,i+2*s-1,t); i=i+2*s;
}
if(i<(n-s+1)) 8 / 33
// k为存入t中的数的位置； //依次排列两组数据
//将第一组数据与第二组数据分别比较； //第一组数据先排完的情况
//对数据进行每组s个数的归并排序；
//i为要合并两组元素的第一个数位置； //i+s-1为要合并的第一组元素的最后一
//数位置、i+2*s-1 为要合并的两组元素 //最后一个数位置；
//考虑n不能被s整除，如果余下的数少于//2*s 但大于s，也就是余下的数不能凑成 //两组，凑一组有余,则把余下的数进行组
数据结构各种排序算法的课程设计实验报告(c语言版)
//合，并对其进行排序；
merge(r,i,i+s-1,n,t);
else //如果余下的数少于s，则余下的数进行组//合，
并进行排序；
}
void gb(FILE *fp) // 归并主函数； {
n = r.length;
while(i<=n)
t.base[i]=r.base[i++];
SqList6 t;
t.base=(char *) malloc(r.stacksize*sizeof(char));
//给待排序的数组t申请内存；
while(s { tgb(s,n,r,t); // s为每组元素的个数、n为元素总个数、r //为原数组，t为待排序的数组，进行归并排 s*=2; //序；把元素个数相同的两组合并 并进行重新 //定义成新的一组，此组元素个数为2*s； if(s //当元素个数小于n时，对其进行合并排序； } } else //当元素个数大于n时，对剩下的数排序； { } i=0; while(i<=n) { } r.base[i]=t.base[i+1]; i++; 3.7冒泡排序 ⑴算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于 9 / 33 数据结构各种排序算法的课程设计实验报告(c语言版) 两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。 ⑵程序实现及核心代码的注释： for( i=0; i < r.length ;i++ ) // i为排好序的数的下标，依次往后存放排好序的数； { for( j = r.length-2;j >= i;j -- ) //从后往前依次两两比较，较小的被调换到前面 ； if(r.base[j+1] < r.base[j]) //比较相邻两个数，如果后面的小于前面的，向下执行； { temp = r.base[j+1]; //将后面的较小的数保存起来； r.base[j+1] = r.base[j]; //将前面的较大的数放在后面较小的数的位置； r.base[j] = temp; //将较小的数放在前面的较大的数的位置； } } 4.调试 检测主函数是否能够稳定运行(如图4-1)： 图4-1 10 / 33