.XX职业技术师X大学课程设计任务书理学院数学0902班学生（16）马新月课程设计课题：16、综合排序：利用随机函数随机产生N=200个随机整数，对这些数进行多种方法的排序。
要求：1）至少采用三种方法实现上述问题求解（插入排序、希尔排序、冒泡排序、快速排序、堆排序、归并排序）。
把排序后的结果存在不同的文件中。
2）记录不同排序方法的运行时间，找出自己排序方法中最快的两种方法。
3）统计每种算法所用的比较次数和交换次数，以列表显示出来。
一、课程设计工作日自2012 年2月21日至2012年3月4日二、同组学生：马新月三、课程设计任务要求（包括课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：课题来源：教师提供课题类型：设计课程设计的目的1)使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。
2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规X化软件设计的能力。
3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力XX职业技术师X大学课程设计评审表学院班学生1概要1.1设计目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。
学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。
通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。
1）本演示程序对以下6种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；2）待排序表的元素的关键字为整数。
比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；4）最后对结果作出简单分析。
1.2预期目标按要求输入不同的操作。
输入后，根据不同的输入进行不同的操作，最终达到对各算法进行比较的目的。
通过此次课程设计主要达到以下目的了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规X进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
2排序算法2.1各排序算法的特点1）冒泡排序冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。
即首先比较第1个和第2个数，将大数放前，小数放后。
然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。
重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。
如此下去，直至最终完成排序。
由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以称作冒泡排序。
2）直接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
3）简单选择排序（1）在一组元素V[i]~V[n-1]中选择具有最小排序码的元素（2）若它不是这组元素中的第个元素，则将它与这一组元素中的第一个元素对调；（3）在这组元素中剔除这个具有最小排序码的元素，在剩下的元素V[i+1]~V[n-1]中重复执行第（1）（2）步，直到剩余元素只有一个为止。
4）快速排序首先检查数据列表中的数据数，如果小于两个，则直接退出程序。
如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序；5）希尔排序先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止；6) 堆排序堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素；堆的定义: N个元素的序列K1，K2，K3，...，Kn.称为堆，当且仅当该序列满足特性：Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])；2.2各算法的比较方法1.稳定性比较插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3.辅助空间的比较线形排序的辅助空间为O(n),其它排序的辅助空间为O(1);4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限X围内时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序3流程图及详细算法3.1流程图函数的调用关系图反映了演示程序的层次结构：图3.1 流程图3.2流程图模块说明1）Main为主函数模块2）bubblesort，insertsort，selectsort，quicksort，shellsort，heansort分别对应冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序的各函数模块3）在初始化数据之后，选择对应的排序模块进行排序，并对排序做出比较3.3可排序表的抽象数据类型定义：typedef struct{ //定义一个RedType型结构体，存放关键字int key; //关键字为整型} RedType;class LinkList //定义一个顺序表{public:RedType r[MAXSIZE+1]; //长度为MAXSIZE+1的数组r，数组里每个元素均为RedTypeint Length; //数组长度int CmpNum, ChgNum; //关键字的比较次数，移动次数LinkList(); //构造函数bool LT(int i, int j); //比较i和j的大小void Display(); //输出数组元素void Insert( int dk); //插入排序void ShellSort(); //希尔排序int Partition( int low, int high); //比基准小的数放左边，比起大的数放右边，返回基准位置void QSort( int low, int high); //从low到high位置进行快速排序void QuickSort(); //对有序表进行快速排序void HeapAdjust( int s, int m); //将无序堆调整为大顶堆void HeapSort(); //堆排序，将大顶堆转换为小顶堆void BubbleSort(); //冒泡排序int SelectMinKey( int k); //找到数组中最小值，返回最小值位置void SelSort(); //对顺序表进行选择排序void SelectSort(); //界面设计void AllAbove(); //统计以上所有排序关键字的比较次数、移动次数及所消耗的时间};3.4程序代码3.4.1 函数声明#include <stdio.h>#include <iostream.h>#include <stdlib.h>#include <string.h>#include <time.h>#include <windows.h>#include <winbase.h>#include <iomanip.h>#define MAXSIZE 1000#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct{int key;} RedType;class LinkList{public:RedType r[MAXSIZE+1];int Length;int CmpNum, ChgNum; LinkList();bool LT(int i, int j);void Display();void Insert( int dk);void ShellSort();int Partition( int low, int high); void QSort( int low, int high); void QuickSort();void HeapAdjust( int s, int m); void HeapSort();void BubbleSort();int SelectMinKey( int k);void SelSort();void SelectSort();void AllAbove();};LinkList::LinkList(){int i;for (i = 0; i <= MAXSIZE; i++)r[i].key = rand()%1000; Length=MAXSIZE+1; CmpNum=0;ChgNum=0;}bool LinkList::LT(int i, int j){ (CmpNum)++;if (i < j)return TRUE;elsereturn FALSE;}void LinkList::Display(){int j;for(int i=0;i<=MAXSIZE;i++){cout<<setw(6)<<r[i].key;if(++j%10==0)cout<<endl;}cout<<endl;}4.3.2六种排序算法代码//插入排序void LinkList::Insert(int dk){int i, j;RedType Temp;for (i = dk; i < Length; i++){if (LT(r[i].key, r[i - dk].key)){memcpy(&Temp, &r[i], sizeof(RedType));for (j = i - dk; j >= 0 && LT(Temp.key, r[j].key); j -= dk){(ChgNum)++;memcpy(&r[j + dk], &r[j], sizeof(RedType));}memcpy(&r[j + dk], &Temp, sizeof(RedType));}}}//希尔排序void LinkList::ShellSort(){int t=Length+1;do{t=t/3+1;Insert( t);}while(t>1);}//快速排序int LinkList::Partition(int low, int high){RedType Temp;int PivotKey;memcpy(&Temp, &r[low], sizeof(RedType));PivotKey = r[low].key;while (low < high){while (low < high &&r[high].key >= PivotKey){high--;(CmpNum)++;}(ChgNum)++;memcpy(&r[low], &r[high], sizeof(RedType));while (low < high && r[low].key <= PivotKey){low++;(CmpNum)++;}(ChgNum)++;}memcpy(&r[low], &Temp, sizeof(RedType)); return low;}void LinkList::QSort( int low, int high){int PivotLoc = 0;if (low < high){PivotLoc = Partition( low, high);QSort(low, PivotLoc - 1);QSort( PivotLoc + 1, high);}}void LinkList::QuickSort(){QSort(0, Length - 1);}//堆排序void LinkList::HeapAdjust(int s, int m){RedType Temp;int j = 0;s++;memcpy(&Temp, &r[s - 1], sizeof(RedType)); for (j = 2 * s; j <= m; j *= 2){if (j < m && LT(r[j - 1].key, r[j].key))++j;if (!LT(Temp.key, r[j - 1].key))break;(ChgNum)++;memcpy(&r[s - 1], &r[j - 1], sizeof(RedType));s = j;}memcpy(&r[s - 1], &Temp, sizeof(RedType));}void LinkList::HeapSort(){int i = 0;RedType Temp;for (i = Length / 2-1; i >= 0; i--)HeapAdjust(i, Length);for (i = Length; i > 1; i--){memcpy(&Temp, &r[0], sizeof(RedType));(ChgNum)++;memcpy(&r[0], &r[i - 1], sizeof(RedType));HeapAdjust( 0, i - 1);}}//冒泡排序void LinkList::BubbleSort(){int i, j;RedType temp;for (i = 1; i <= MAXSIZE; i++){for (j = 1; j <= MAXSIZE - i; j++){if (!LT(r[j].key, r[j + 1].key)){(ChgNum)++;memcpy(&temp, &r[j], sizeof(RedType));memcpy(&r[j], &r[j + 1], sizeof(RedType));memcpy(&r[j + 1], &temp, sizeof(RedType));}}}}//选择排序int LinkList::SelectMinKey( int i){int Min = i;for (int k=i; k < Length; k++){if (!LT(r[Min].key, r[k].key))Min = k;}return Min;}void LinkList::SelSort(){int i, j;RedType temp;for (i = 0; i < Length; i++){j = SelectMinKey( i);if (i != j){(ChgNum)++;memcpy(&temp, &r[i], sizeof(RedType));memcpy(&r[i], &r[j], sizeof(RedType));memcpy(&r[j], &temp, sizeof(RedType));}}}4.3.3 排序算法的选择void LinkList::SelectSort(){cout<<"1. 插入排序"<<endl;cout<<"2. 希尔排序"<<endl;cout<<"3. 快速排序"<<endl;cout<<"4. 堆排序"<<endl;cout<<"5. 冒泡排序"<<endl;cout<<"6. 选择排序"<<endl;cout<<"7. 以上各种排序"<<endl;cout<<"8. 退出程序"<<endl;cout<<"请选择需要进行的操作:"<<endl;}void LinkList::AllAbove(){int TempTime;int SpendTime;cout<<endl;LinkList();cout<<"插入排序:"<<endl;TempTime = (int)GetTickCount();Insert( 1);SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;LinkList();//随机数列复位cout<<endl;cout<<"希尔排序:"<<endl;TempTime = (int)GetTickCount();ShellSort();SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;LinkList(); //随机数列复位cout<<endl;cout<<"快速排序:"<<endl;TempTime = (int)GetTickCount();QuickSort();SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;LinkList(); //随机数列复位cout<<endl;cout<<"堆排序:"<<endl;TempTime = (int)GetTickCount();HeapSort();SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;LinkList(); //随机数列复位cout<<endl;cout<<"冒泡排序:"<<endl;TempTime = (int)GetTickCount();BubbleSort();SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;LinkList(); //随机数列复位cout<<endl;cout<<"选择排序:"<<endl;TempTime = (int)GetTickCount();SelSort();SpendTime = (int)GetTickCount() - TempTime;cout<<endl;cout<<"pareNumber="<<CmpNum<<" "<<"ChageNumber="<<ChgNum<<" "<<"TimeSpent="<<SpendTime<<"ms"<<endl;}4.3.4主函数程序代码void main(){int i,j;int select = 0;int SpendTime = 0;int TempTime;do{LinkList L;L.SelectSort();cin>>select;switch (select){case 1:cout<<"插入排序前:"<<endl;L.Display();cout<<"插入排序后:"<<endl;TempTime = (int)GetTickCount();L.Insert(1);SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 2:cout<<"希尔排序前:"<<endl;L.Display();cout<<"希尔排序后:"<<endl;cout<<endl;TempTime = (int)GetTickCount();L.ShellSort();SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 3:cout<<"快速排序前:"<<endl;L.Display();cout<<"快速排序后:"<<endl;TempTime = (int)GetTickCount();L.QuickSort();SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 4:cout<<"堆排序前:"<<endl;L.Display();cout<<"堆排序后:"<<endl;TempTime = (int)GetTickCount();L.HeapSort();SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 5:cout<<"冒泡排序前:"<<endl;L.Display();cout<<"冒泡排序后:"<<endl;TempTime = (int)GetTickCount();L.BubbleSort();SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 6:cout<<"选择排序前:"<<endl;L.Display();cout<<"选择排序后:"<<endl;TempTime = (int)GetTickCount();L.SelSort();SpendTime = (int)GetTickCount() - TempTime;L.Display();cout<<endl;cout<<"比较次数="<<L.CmpNum<<" "<<"关键字移动次数="<<L.ChgNum<<" "<<"所需时间="<<SpendTime<<"ms"<<endl;break;case 7:L.AllAbove();break;default:cout<<"please input numbers again"<<endl;break;}}while(select!=8);}4运行结果4.1调试分析1．对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法的比较测试，得到的测试数据具有较好的典型性和可比较性。