1、内部排序比较 哈尔滨理工大学课 程 设 计 （数据结构）题 目：内部排序算法比较班 级：姓 名：指导教师：系主任： 2013年3月7号 目 录1（内部排序算法）问题课程设计3 1.1题目分析3 1.2数据结构3 1.3流程图4 1.4实现技术5 1.5设计结论和心得62. （C+）代码分析7 2.1功能说明13 2.2局部数据结构132.3流程图141内部排序课程设计1.1 题目分析对各种内部排序算法的时间复杂度有一个比较直观的感受，包括关键字比较次数和关键字移动次数。将排序算法进行合编在一起，可考虑用顺序执行各种排序算法来执行，最后输出所有结果。1.2 数据结构本程序中，考虑的内容就是待排序
2、对象，排序的依据是关键字之间的大小比较，故在每个节点的类型定义中，至少得包含关键字key一项。不失一般性，这里就使用关键词这一项，其他都省略，具体应用加上其他数据项即可。被排序对象是由一个个节点够成，一个排序对象包含一系列指向一串节点的指针，排序对象的长度。本程序功能简单。typedef structint key; /*关键字*/RecordNode; /*排序节点的类型*/typedef struct RecordNode *record; int n; /*排序对象的大小*/SortObject; /*排序节点的类型*/用伪代码表示如下1）冒泡排序算法伪代码 bubblesoft（dat
3、a ） for i=1to data.length-2 for j=data.length-1 downto j+1 如果顺序错误就交换j和j-1的位置上元素； 2）选择排序算法伪代码 selectionsoft（data ） for i=1to data.length-2 从datai，datadata.length-1中选取最小的元素 将它和datai交换； 3）插入排序算法伪代码 insertionsoft（data ） for i=1todata.length-1 tmp =datai; 将所有大于tmp的元素dataj移动一个位置； 把tmp放到正确的位置上； 为了实现这些数据结构，
4、用C语言定义变量如下：int Create_Sq(SqList &L)void Bubble_sort(SqList &L)/冒泡排序void InsertSort(SqList &L)/插入排序 void SelectSort(SqList &L) /简单选择排序int Partition(SqList &L,int low,int high)void QSort(SqList &L,int low,int high)/递归形式的快速排序算法void QuickSort(SqList &L)void ShellInsert(SqList &L,int dk)/希尔排序 void ShellS
5、ort(SqList &L,int dlta 1.3 流程图1.4 实现技术实现步骤如下：1.待排序长度不小于100，数据可有随机函数产生，用五组不同输入数据做比较，比较的指标为关键字参加比较的次数和关键字移动的次数；2.对结果做简单的分析，包括各组数据得出结果的解释；3.设计程序用顺序存储。运行结果如下：元素个数为20元素个数为1001.5 设计结论和心得（1）实验中的存在问题和提高存在问题：程序有待增强。提高：界面处理简洁。（2）收获与体会各种排序的算法排序的算法的比较次数与移动次数的计算随机数的生成2.代码分析为了进一步了解操作系统内核，学习了Linux操作系统的进程同步程序，主要程序源
6、代码如下：#include #include using namespace std;#define LS(a,b) (a)(b)#define MAXSIZE 10000typedef int KeyType;typedef struct KeyType key;RedType;typedef struct RedType rMAXSIZE+1;int length;SqList;int compare=0;int change=0;int Create_Sq(SqList &L)int k;coutk;L.length=k;srand(time(NULL); for (int x=1; x
7、=k; x+) L.rx.key= rand() % k;/随机域为0k return 1; void Bubble_sort(SqList &L)/冒泡排序 int i,j,l,k=L.length,m=0,n=0;for(i=1;i=L.length-1;+i) for(j=1;j=k-1;+j) +m; if(LL(L.rj.key,L.rj+1.key) l=L.rj.key; L.rj.key=L.rj+1.key; L.rj+1.key=l; +n; -k;coutendl-冒泡排序后的序列-endl;for(i=1;i=L.length;i+) cout L.ri.key;cou
8、tendl;cout冒泡排序的比较次数:;coutmendl;cout冒泡排序的交换次数:;coutnendl; void InsertSort(SqList &L)/插入排序 int i,j,m=0,n=0;coutendl; for(i=2;i=L.length;+i) if(LS(L.ri.key,L.ri-1.key) +m; +n; L.r0=L.ri; L.ri=L.ri-1; for(j=i-2;LS(L.r0.key,L.rj.key);-j) +m; L.rj+1=L.rj; L.rj+1=L.r0; cout-直接插入排序后的序列-endl;for(i=1;i=L.leng
9、th;i+) cout L.ri.key;coutendl;cout直接插入排序的比较次数:;coutmendl;cout直接插入排序的交换次数:;coutnendl; void SelectSort(SqList &L) /简单选择排序 int l,i,j,m=0,n=0;coutendl;for(i=1;iL.length;+i) L.r0=L.ri; j=i+1; l=i; for(j;j=L.length;+j) +m; if(LL(L.r0.key,L.rj.key) l=j; L.r0=L.rj; if(l!=i) +n; L.rl=L.ri; L.ri=L.r0; cout-简单
10、选择排序后的序列-endl;for(i=1;i=L.length;i+)cout L.ri.key;coutendl;cout简单选择排序的比较次数:;coutmendl;cout简单选择排序的交换次数:;coutnendl; int Partition(SqList &L,int low,int high)int pivotkey;L.r0=L.rlow;pivotkey=L.rlow.key;while(lowhigh) while(low=pivotkey) +compare; -high; +change; L.rlow=L.rhigh; while(lowhigh&L.rlow.ke
11、y=pivotkey) +compare; +low; +change; L.rhigh=L.rlow;L.rlow=L.r0;return low; void QSort(SqList &L,int low,int high)/递归形式的快速排序算法int pivotloc;if(lowhigh) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L)int i;QSort(L,1,L.length);cout-快速排序后的序列为-
12、endl;for(i=1;i=L.length;i+)cout L.ri.key;coutendl;cout快速排序的比较次数:;coutcompareendl;cout快速排序的交换次数:;coutchangeendl;compare=0;change=0; void ShellInsert(SqList &L,int dk)/希尔排序 int i;int j;for(i=dk+1;i0&LS(L.r0.key,L.rj.key);j-=dk) +compare; +change; L.rj+dk=L.rj; L.rj+dk=L.r0; void ShellSort(SqList &L,in
13、t dlta)/希尔排序 int k,j=L.length/2,t=0;while(j=0) +t; j-=2;j=L.length/2;for(k=0;kt;+k)/计算每次的增量值 if(j=0) j=1;/定义最后一趟排序的增量 dltak=j; j-=2;for(k=0;kt;+k) ShellInsert(L,dltak);cout-希尔排序后的序列为-endl;for(k=1;k=L.length;k+) cout L.rk.key;coutendl;cout希尔排序的比较次数:;coutcompareendl;cout希尔排序的交换次数:;coutchangeendl;compa
14、re=0;change=0; /*这里是改造后的main，他的原始形式是dev自动生成的*/ int main(int argc, char *argv) int i;int dltaMAXSIZE;SqList L,a,b,c,d;Create_Sq(L);a=b=c=d=L;for(i=1;i=L.length;i+)cout L.ri.key; Bubble_sort(L);InsertSort(a);SelectSort(b);QuickSort(c);ShellSort(d,dlta);/*这两行是系统自动生成的main中的内容，不要删了 */ system(PAUSE);retur
15、n EXIT_SUCCESS;2.1 功能说明这一段程序的主要功能为：希尔排序O（n1.3）O（1）时间复杂度与空间复杂度：理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：影响排序的因素： 待排序的记录数目n 的大小。 记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。 关键字的结构及其分布情况。 对排序稳定性的要求2.2局部数据结构本程序有局部变量及数据结构，其类型定义及语义如下：typedef struct KeyType key;RedType;typedef struct RedType rMAXSIZE+1;int length;SqList;2.3流程图2.4以实例说明运行过程元素个数为20 元素个数为100
