目录
1.引言............................................................................................................................ 错误！未定义书签。
2.需求分析 (2)
3.详细设计 (2)
3.1 直接插入排序 (2)
3.2折半排序 (2)
3.3 希尔排序 (4)
3.4简单选择排序 (4)
3.5堆排序 (4)
3.6归并排序 (5)
3.7冒泡排序 (7)
4.调试 (8)
5.调试及检验 (9)
5.1 直接插入排序 (9)
5.2折半插入排序 (9)
5.3 希尔排序 (10)
5.4简单选择排序 (10)
5.5堆排序 (11)
5.6归并排序 (12)
5.7冒泡排序 (12)
6.测试与比较................................................................................................................ 错误！未定义书签。
6.1调试步骤......................................................................................................... 错误！未定义书签。
6.2结论 (13)
7.实验心得与分析 (13)
8.附录 (15)
8.1直接插入排序 (15)
8.2折半插入排序 (16)
8.3希尔排序 (18)
8.4简单选择排序 (20)
8.5堆排序 (21)
8.6归并排序 (24)
8.7冒泡排序 (27)
8.8主程序 (28)
1.需求分析
课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。
为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。
软件环境：
Windows-7操作系统，所使用的软件为c-Free；
2.概要设计
2.1 直接插入排序
⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。
⑵程序实现及核心代码的注释：
for (i = 1 ; i < r.length ;++i )
for(j=0;j < i;++j)
if(r.base[i] < r.base[j])
{
temp = r.base[i]; //保存待插入记录
for(i= i ;i > j; --i )
r.base[i] = r.base[i-1]; //记录后移
r.base[j] = temp; //插入到正确的为位置
}
r.base[r.length] ='\0';
2.2折半排序
⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O（n2）。
⑵程序实现及核心代码的注释：
void zb(FILE *fp)
{ //对顺序表作折半插入排序for ( i = 1 ; i < r.length ; i++ )
{
temp=r.base[i]; //将r.base[i]寄存在temp中
low=0;
high=i-1;
while( low <= high ) //在base[low]到key[high]中折
半查找有序插入的位置{
m = (low+high)/2; //折半
if ( temp < r.base[m] )
high = m-1; //插入低半区
else
low = m+1; //插入高半区
}
for( j=i-1; j>=high+1; --j )
r.base[j+1]= r.base[j]; //记录后移
r.base[high+1]=temp; //插入
}
2.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; //插入
}
}
2.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;
}
2.5堆排序
⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉
