数据结构课程设计排序算法集成
数据结构课程设计排序算
法集成
The Standardization Office was revised on the afternoon of December 13, 2020
xx大学
本科生课程设计论文
题目：排序算法集成
学生姓名：
学号：
专业：计算机
班级：
指导教师：
2013年 5月20日
xx大学课程设计任务书
目录
目录 (3)
引言 (4)
一．算法的设计思想 (4)
二．算法的流程图 (4)
三．算法的设计与分析 (5)
建立数组 (5)
算法思想................................................................................................ 错误!未定义书签。
主要函数 (6)
主要函数声明............................................................................... 错误!未定义书签。
主要变量说明 (10)
四．程序源代码 (11)
五．运行结果与分析（测试） (18)
六．总结（收获与体会） (20)
七．参考文献 (21)
引言
本课程设计主要解决几种不同排序方法以及在各种不同排序的过程中某一趟的具体排序结果。通过观察各种排序的具体排序过程，加深对不同排序方法的认识，加深对不同排序算法的掌握。
一．算法设计的思想
数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。
排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。
完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。
据对题目的分析，首先要根据插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。内部排序的方法很多，但就其全面性而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境。通常，在排序的过程中需进行两种基
本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。
二．算法的流程图
如图
图主要设计思想流程图
三．算法的设计与分析
建立数组
在程序中建立一个数组data[ ]，用于存储程序运行中的数据。
算法思想
（1）插入排序
插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。
（2）希尔排序
希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
（3）冒泡排序函数
冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。
（4）选择排序函数
选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
（5）堆排序
先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。
主要函数
（1）插入排序函数
void insertion_sort(int[],int);/*插入排序*/
（2）希尔排序函数
void shell_sort(int[],int);/*希尔排序*/
（3）冒泡排序函数
void bubble_sort(int[],int);/*冒泡排序*/
（4）选择排序函数
void select_sort(int[],int);/*选择排序*/
（5）将数据调整为堆的函数
void adjust(int,int);/*将数据调整为堆树*/
主要函数声明
①插入排序
插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。
void insertion_sort(int data[],int size)/*插入排序*/
{int base,compare,temp,i,j=0;
for(base=1;base 否则与后面数据对比找出插入位置*/ {temp=data[base]; compare=base; j++; while(compare>0 && data[compare-1]>temp) {data[compare]=data[compare-1]; compare--; } data[compare]=temp; printf("第%d 趟排序:" ,j); for(i=0;i printf("%d ",data[i]); printf("\n"); } printf("\n最终排序结果:"); for(i=0;i printf("%d ",data[i]); printf("\n"); } ②希尔排序 希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 void shell_sort(int data[],int size)/*希尔排序*/ { int i,j,k,incr,temp,num=0; incr=size/2; printf("\n"); while(incr>0) { for(i=incr+1;i {j=i-incr; while(j>0) if(data[j]>data[j+incr])/*比较每部分的数据大小顺序不对则交换*/ { temp=data[j]; data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr; } else j=0; } num++; printf("\n第%d 趟排序:",num); for(k=1;k printf("%d ",data[k]); incr=incr/2; } printf("\n最终排序结果："); for(i=1;i printf("%d ",data[i]); printf("\n"); } ③冒泡排序 冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。 void bubble_sort(int data[],int size)/*冒泡排序*/ {int i,j,flag,k,temp,num=0; for(i=0;i {flag=0; for(j=0;j {if(data[j]>data[j+1]) {flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; } num++; printf("\n第%d趟排序：",num); for(k=0;k printf("%d ",data[k]); printf("\n"); } printf("\n最终排序结果："); for(i=0;i printf("%d ",data[i]); printf("\n"); if(flag!=1) break; } } ④选择排序 选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。 void select_sort(int data[],int size)/*选择排序*/ {int base,compare,min,temp,i,num=0; for(base=0;base for(compare=base+1;compare if(data[compare] min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp; num++; printf("第%d趟排序：",num); for(i=0;i printf("%d ",data[i]); printf("\n"); } printf("\n最终排序结果："); for(i=0;i printf("%d ",data[i]); printf("\n"); } 主要变量说明 Int data[] :整型数组，用于储存序列 Int size:整型变量，用于记录序列长度 Int temp:整型变量，用于交换元素 Int m,n,k,i,j,num:一般整型变量 四．程序源代码 #include<> void insertion_sort(int[],int);/*插入排序*/ void shell_sort(int[],int);/*希尔排序*/ void bubble_sort(int[],int);/*冒泡排序*/ void select_sort(int[],int);/*选择排序*/ void adjust(int,int);/*将数据调整为堆树*/ void insertion_sort(int data[],int size)/*插入排序*/ {int base,compare,temp,i,j=0; for(base=1;base {temp=data[base]; compare=base; j++; while(compare>0 && data[compare-1]>temp) {data[compare]=data[compare-1]; compare--; } data[compare]=temp; printf("第%d 趟排序:" ,j); for(i=0;i printf("%d ",data[i]); printf("\n"); } printf("\n最终排序结果:"); for(i=0;i printf("%d ",data[i]); printf("\n"); } void shell_sort(int data[],int size)/*希尔排序*/ { int i,j,k,incr,temp,num=0; incr=size/2; printf("\n"); while(incr>0) { for(i=incr+1;i {j=i-incr; while(j>0) if(data[j]>data[j+incr])/*比较每部分的数据大小顺序不对则交换*/ { temp=data[j]; data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr; } else j=0; } num++; printf("\n第%d 趟排序:",num); for(k=1;k printf("%d ",data[k]); incr=incr/2; } printf("\n最终排序结果："); for(i=1;i printf("%d ",data[i]); printf("\n"); } void bubble_sort(int data[],int size)/*冒泡排序*/ {int i,j,flag,k,temp,num=0; for(i=0;i {flag=0; for(j=0;j { flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; } num++; printf("\n第%d趟排序：",num); for(k=0;k printf("%d ",data[k]); printf("\n"); } printf("\n最终排序结果："); for(i=0;i printf("%d ",data[i]); printf("\n"); if(flag!=1) break; } } void select_sort(int data[],int size)/*选择排序*/ {int base,compare,min,temp,i,num=0; for(base=0;base for(compare=base+1;compare if(data[compare] min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp; num++; printf("第%d趟排序：",num); for(i=0;i printf("%d ",data[i]); printf("\n"); } printf("\n最终排序结果："); for(i=0;i printf("%d ",data[i]); printf("\n"); } void adjust(int i,int n)/*将数据调整为堆树*/ {int data[20],j,k,done=0; k=data[i]; j=2*i; while((j<=n)&&(done==0)) {if((j if(k>=data[j])done=1; else {data[j/2]=data[j]; j=2*j; } } data[j/2]=k; } void main() {int data[20]; int size=0,m=0,i,j,num,k,temp,n=0;