实验七 排序及其应用.doc

实验七 排序及其应用 一．实验目的 （1）掌握常用排序方法的基本思想； （2）通过实验加深理解各种排序算法； （3）通过实验掌握各种排序方法的时间复杂度分析； （4）了解各种排序方法的优缺点及适用范围。 二．实验内容 （1）编写直接插入排序程序； （2）编写希尔排序程序； （3）编写冒泡排序程序； （4）编写快速排序程序； （5）编写选择排序程序； （6）编写归并排序程序； （7）编写堆排序程序； （8）程序执行时，要求能显示每一趟的排序结果； （9）设计一个选择式菜单，以菜单方式选择上述排序程序。 排 序 子 系 统 *************************************************** * 1------------更新排序数据 * * 2------------直接插入排序 * * 3------------希 尔 排 序 * * 4------------冒 泡 排 序 * * 5------------快 速 排 序 * * 6------------选 择 排 序 * * 7------------归 并 排 序 * * 8------------堆 排 序 * * 0------------返 回 * *************************************************** 请选择菜单项： 三.基本原理 请叙述希尔排序、快速排序、选择排序和堆排序的基本思想。 四、程序模板 #include stdio.h #include stdlib.h #include math.h #define L 8 #define FALSE 0 #define TRUE 1 typedef struct { int key; char otherinfo; }RecType; typedef RecType Seqlist[L+1]; int num; Seqlist R; void Insertsort(); void Bubblesort(); void QuickSort(int low,int high); void Shellsort(); void Selectsort(); void Mergesort(); void Partition(); void Heap(); void main() { Seqlist S; int i,k; char ch1,ch2,q; printf(\n\t请输入%d个待排序数据：（按回车隔开）\n\t,L); for(i=1;i=L;i++) { scanf(%d,S[i].key);getchar();printf(\t); } printf(\n\t排序数据已经输入完毕！); ch1=y; while (ch1==y||ch1==Y) { printf(\n\n\n\n\n\t\t\t排 序 子 系 统\n); printf(\t\t***************************************\n); printf(\t\t* 1--------更新排序数据----------*\n); printf(\t\t* 2--------直接插入排序 ---------*\n); printf(\t\t* 3--------希 尔 排 序 ---------*\n); printf(\t\t* 4--------冒 泡 排 序 ---------*\n); printf(\t\t* 5--------快 速 排 序----------*\n); printf(\t\t* 6--------选 择 排 序 ---------*\n); printf(\t\t* 7--------归 并 排 序 ---------*\n); printf(\t\t* 8--------堆