排序

课程名称: 《数据结构》课程设计课程设计题目: 排序姓名:院系: 计算机科学与技术学院专业: 计算机科学与技术年级: 2011级学号:指导教师: 王爱平2013 年 9月 14 日目录1 课程设计的目的 (3)2 需求分析 (3)3 课程设计报告内容 (3)3.1概要设计 (3)3.2详细设计 (4)3.3调试分析 (4)3.4用户手册 (4)3.5测试结果 (4)4 小结 (4)5程序清单 (4)6 参考文献 (9)7 程序截图 (9)1.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析各种排序算法性能比较利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。

要求：①至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、2-路插入排序、希尔排序、起泡排序、改进的冒泡排序、快速排序、选择排序、堆排序、归并排序、三部排序、计数排序、鸽巢排序、鸡尾酒排序、地精排序、奇偶排序、梳排序、耐心排序——标红的至少选择一种）。

并把排序后的结果保存在不同的文件中。

②统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3 排序的设计3.1概要设计typedef int ElemType;链表数据结构：typedef struct SqList{ElemType *elem;int length;}SqList, *PList;3.2详细设计void InitSqList(PList List)//函数功能:链表初始化void RandomElemToSqList(PList List)//函数功能:用随机数填充链表void CopySqList(PList List1, PList List2)//函数功能:链表复制void SqListToFile(PList List, FILE *fp)//函数功能:将链表的内容写入文件void InsertSort(PList List)//函数功能:插入排序int Partition(PList List, int low, int high)//函数功能:将链表分成两部分，前面小于pivotkey，后面大于pivotkeyvoid QSort(PList List, int low, int high)//函数功能:快速排序void GnomeSort(PList List)//函数功能:地精排序,冒泡排序的变种void PigeonholeSort(PList List)//函数功能:鸽巢排序3.3调试分析(略)3.4用户手册(略)3.5测试结果(略)4总结（略）5、程序清单:#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>#define MAX 80000typedef int ElemType;typedef struct SqList{//链表ElemType *elem;int length;}SqList, *PList;void InitSqList(PList);void RandomElemToSqList(PList);void CopySqList(PList, PList);void SqListToFile(PList, FILE *);void InsertSort(PList);void QSort(PList, int, int);void GnomeSort(PList);void PigeonholeSort(PList);int Partition(PList, int, int);int main(){FILE *fp;long start, end;SqList List1, List2, List3, List4;InitSqList(&List1);InitSqList(&List2);InitSqList(&List3);InitSqList(&List4);RandomElemToSqList(&List1);CopySqList(&List2, &List1);CopySqList(&List3, &List1);CopySqList(&List4, &List1);printf("**********排序元素个数%d***********\n", MAX); fp = fopen("QSort.txt", "w");printf(" 快速排序用时:");start = clock();QSort(&List1, 1, MAX);end = clock();printf("%6dms\n", end-start);SqListToFile(&List1, fp);fclose(fp);fp = fopen("InsertSort.txt", "w");printf(" 插入排序用时:");start = clock();InsertSort(&List2);end = clock();printf("%6dms\n", end-start);SqListToFile(&List2, fp);fclose(fp);fp = fopen("GnomeSort.txt", "w");printf(" 地精排序用时:");start = clock();GnomeSort(&List3);end = clock();printf("%6dms\n", end-start);SqListToFile(&List3, fp);fclose(fp);fp = fopen("PigeonholeSort.txt", "w");printf(" 鸽巢排序用时:");start = clock();PigeonholeSort(&List4);end = clock();printf("%6dms\n", end-start);SqListToFile(&List4, fp);return 0;}void InitSqList(PList List)//函数功能:链表初始化{if(!(List->elem = (ElemType *)malloc((MAX+1)*sizeof(ElemType)))) exit(1);List->length = MAX;}void RandomElemToSqList(PList List)//函数功能:用随机数填充链表{time_t t;ElemType k;int i;srand((unsigned)time(&t));for(i=1; i<=List->length; i++){k = rand()%MAX;List->elem[i] = k;}}void CopySqList(PList List1, PList List2)//函数功能:链表复制{int i;for(i=1; i<=List2->length; i++){List1->elem[i] = List2->elem[i];}List1->length = List2->length;}void SqListToFile(PList List, FILE *fp)//函数功能:将链表的内容写入文件{int i;for(i=1; i<=List->length; i++){fprintf(fp, "%6d ", List->elem[i]);if(i%17 == 0)fprintf(fp, "\n");}}void InsertSort(PList List)//函数功能:插入排序{int i, j;for(i=2; i<=List->length; i++){if(List->elem[i]<List->elem[i-1]){List->elem[0] = List->elem[i];List->elem[i] = List->elem[i-1];for(j=i-2; ; j--){if(List->elem[0]>List->elem[j])break;List->elem[j+1] = List->elem[j];}List->elem[j+1] = List->elem[0];}}}int Partition(PList List, int low, int high)//函数功能:将链表分成两部分，前面小于pivotkey，后面大于pivotkey{ElemType pivotkey;List->elem[0] = List->elem[low];pivotkey = List->elem[low];while(low<high){while(low<high && List->elem[high]>=pivotkey)--high;List->elem[low] = List->elem[high];while(low<high && List->elem[low]<=pivotkey)++low;List->elem[high] = List->elem[low];}List->elem[low] = List->elem[0];return low;}void QSort(PList List, int low, int high)//函数功能:快速排序{int pivotloc;if(low<high){pivotloc = Partition(List, low, high);QSort(List, low, pivotloc-1);QSort(List, pivotloc+1, high);}}void GnomeSort(PList List)//函数功能:地精排序,冒泡排序的变种{int i = 1;ElemType e;while(i<List->length){if(1 == i || List->elem[i-1] <= List->elem[i]){i++;continue;}else{e = List->elem[i];List->elem[i] = List->elem[i-1];List->elem[i-1] = e;i--;continue;}}}void PigeonholeSort(PList List)//函数功能:鸽巢排序{int i, j, k=1;ElemType *ph;if(!(ph = (ElemType *)malloc(MAX*sizeof(ElemType)))){printf("溢出\n");return;}for(i=0; i<MAX; i++)ph[i] = 0;for(i=1; i<=List->length; i++){ph[List->elem[i]]++;}for(i=0; i<MAX; i++){for(j=0; j<ph[i]; j++)List->elem[k++] = i;}}6、参考文献1 严蔚敏，吴伟民编著. 数据结构(C 语言版)--北京: 清华大学出版社，2007.2 严蔚敏，吴伟民米宁编著. 数据结构题集(C 语言版)--北京: 清华大学出版社，2007.3网上搜索相关程序作为参考7、程序运行结果运行截图快速排序：插入排序：地精排序：鸽巢排序：11。