排序
- 格式：pdf
- 大小：164.41 KB
- 文档页数：6
陕西科技大学实验报告
班级物联网122学号201206100219姓名王冰杰实验组别
实验日期室温报告日期成绩
报告内容：(目的和要求，原理，步骤，数据，计算，小结等)实验名称：实验八排序算法及应用
一、实验目的：
1.掌握排序的概念。
2.掌握排序的结构定义以及直接插入排序。
3.折半插入排序，希尔排序三种排序算法。
二．实验环境：Codeblocks13
三、实验内容：
1.定义一个线性表，并无序输入n个数，作为表中的元素。
输出排序
后的数。
四、实验涉及知识点：
1.排序方法的稳定性是衡量排序方法的标准。
2.内部排序可在不同的存储结构上实现，顺序表可随机存储。
3.直接插入排序从第二个数据元素开始，依次将数据元素插入到有序
排序中；
4.折半插入排序与直接类似，减少了比较次数；
5.希尔排序根据增量不同，时效高。
6.排序时，插入数据后，相关元素都会向后货向前移动。
五、程序流程分析：
本实验为线性表的基本操作，多采用顺序表或链表。
思想比较简单，流程主要为顺序结构，操作流程图都大致如下：
六、源程序：
对排序的操这些基本操作及数据类型可以先编写入一个头文件4利用书中的算法即可进行，包括初始化顺序表，遍历，直接插入排序，折半插入排序，希尔排序等，将这些便如一个头文件中。
如下所示：
对排序操作的头文件“排序.h”为：
#include "stdio.h"
#include "malloc.h"
/*排序的存储结构*/
#define MAXSIZE 100
typedef int KeyType;
typedef int DataType;
typedef struct{
KeyType key;
DataType data;
}SortItem,SqList[MAXSIZE];
/*直接插入排序*/
void InsertSort(SqList L,int n)
{/*L为待排序的顺序表，n为待排序数据元素个数*/ int i,j;
SortItem p;
for(i=1;i<n;i++)
{
p=L[i];
for(j=i-1;j>=0 && p.key<L[j].key;j--)
L[j+1]=L[j];
L[j+1]=p;
}
}
void BubbleSort(SqList L,int n)
{/*L为待排序的顺序表，n为待排序数据元素个数*/ int i,j,over;
SortItem p;
for(i=0;i<n-1;i++)
{
over=1;
for(j=n-1;j>i;j--)
if(L[j].key<L[j-1].key)
{
p=L[j];
L[j]=L[j-1];
L[j-1]=p;
over=0;
}
if(over) break;
}
}
/*折半插入排序*/
void BiInsertSort(SqList L,int n)
{/*L为待排序的顺序表，n为待排序数据元素个数*/ int i,j,low,upper,mid;
SortItem p;
for(i=1;i<n;i++)
{
p=L[i];
low=0;
upper=i-1;
while(low<=upper)
{
mid=(low+upper)/2;
if(p.key<L[mid].key) upper=mid-1;
else low=mid+1;
}
for(j=i-1;j>=low;j--)
L[j+1]=L[j];
L[low]=p;
}
}
/*希尔排序*/
void ShellSort(SqList L,int n)
{/*L为待排序的顺序表，n为待排序数据元素个数*/ int i,j,d,k;
SortItem p;
for(d=n/2;d>=1;d/=2)
{
p=L[i];
for(j=i-k;j>=0&&p.key<L[j].key;j-=k)
L[j+k]=L[j];
L[j+d]=p;
for(i=0;i<n;i++)
printf("%d\t",L[i].key);
printf("\n\n");
}
}
然后再在对排序进行操作的主程序中先包含头文件“排序.h”该主程序为：
#include <stdio.h>
#include "排序.h"
void main(int argc,char* argv[])
{
SqList L;
KeyType items[]={19,5,46,23,17,55,7};
int i,n=7;
for(i=0;i<n;i++)
L[i].key=items[i];
printf("输出直接插入排序后的结果: ");
printf("\n");
InsertSort(L,n);
//冒泡排序
for(i=0;i<n;i++)
printf("%d\t ",L[i].key);
printf("\n输出冒泡排序后的结果为:\n");
printf("\n");
BubbleSort(L, n);
//折半排序
for(i=0;i<n;i++)
printf("%d\t",L[i].key);
printf("\n输出折半插入排序后的结果为:\n");
printf("\n");
BiInsertSort(L,n);
//希尔排序
for(i=0;i<n;i++)
printf("%d\t",L[i].key);
printf("\n输出希尔排序后的结果为:\n");
printf("\n");
for(i=0;i<n;i++)
printf("%d\t",L[i].key);
printf("\n");
}
七、实验步骤
排序程序的实验步骤：
1.进行Visual Studio开发环境；
2.创建项目：
文件—新建—项目—WIN32项目—输入项目名称test 8；
3.创建头文件和源文件，将预先编制好的程序输入；
4.保存文件；
5.选择调试—开始调试。
八、实验小结
排序实验利运用了三种算法对一组无序数据进行排序，从不同的角度实现了对数据的排序。
实验中，三种排序，直接插入排序简单，较为费时；折半插入排序减少了比较次数，但是复杂度不变；希尔排序时间效率最高。
算法操作时需注意程序的初始定义以及实际操作，避免逻辑方面的细节错误。
实际中根据情况进行选择。
