数据结构实验八-排序.doc

实验八 排序
学生姓名
吴肖遥
学 号
20151681310131
专业班级
电子信息类5班
实验地点
理工大楼610
实验日期
2016.6.13
指导教师
李红蕾
实验环境
Visual c++6.0
实验学时
2学时
实验类型
验证
实验成绩

一、实验目的
1、掌握常用的排序方法，如归并排序、快速排序等。
2、深刻理解排序的定义和排序方法的特点，并能加以灵活应用。
3、能够分析各种算法的效率和适用条件。
二、实验要求
1、认真阅读程序。
2、上机调试，并运行程序。
3、保存和截图程序的运行结果，并结合程序进行分析。
三、实验内容和基本原理
1、实验8.1 归并排序的实现
已知关键字序列为{1,8,6,4,10,5,3,2,22}，请对此序列进行归并排序，并输出结果。见参考程序8.1。

2、实验8.2快速排序的实现
快速排序是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。见参考程序8.2。

参考程序8.1归并排序
#include"stdio.h"
int num=0;
void print_data(int data[],int first,int last)
{
int i=0;
for(i=0;i<first;i++)
printf("*");
for(i=first;i<=last;i++)
printf("%3d",data[i]);
for(i=last;i<=8;i++)
printf("*");
printf("\n");
}
void merge(int array[],int first,int last)/*一趟归并*/
{
int mid,i1,i2,i3;
int temp[10];
int i,j;
mid=(first+last)/2;
i1=0;
i2=first;
i3=mid+1;
while(i2<=mid&&i3<=last)
{
if(array[i2]<array[i3])
temp[i1++]=array[i2++];
else
temp[i1++]=array[i3++];
}
if(i2<=mid)
while(i2<=mid)
temp[i1++]=array[i2++];
if(i3<=last)
while(i3<=last)
temp[i1++]=array[i3++];
for(i=first,j=0;i<=last;i++,j++)
array[i]=temp[j];
print_data(array,first,last);
}
void mergesort(int data[],int first,int last)/*归并排序*/
{
int mid;
if(first<last)
{
mid=(first+last)/2;
mergesort(data,first,mid);
mergesort(data,mid+1,last);
print_data(data,first,last);
merge(data,first,last);
}
}
void main()
{
int a[]={1,8,6,4,10,5,3,2,22};/*可根据实际情况初始化*/
mergesort(a,0,8);
}

参考程序8.2快速排序
#include<iostream.h>
#include"stdio.h"
#define MAX 8
int QuickSort(int a[],int l,int r)
{
int pivot;//枢轴
int i=l;
int j=r;
int tmp;
pivot=a[(l+r)/2];//取数组中间的数为枢轴
do
{
while(a[i]<pivot)
i++;//i右移
while(a[j]>pivot)
j--;//j左移
if(i<=j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;//交换a[i]和a[j]
i++;
j--;
}
}
while(i<=j);
if(l<j)
QuickSort(a,l,j);
if (i<r)
QuickSort(a,i,r);
return 1; }
/*********************************************/
int main()
{ int array[MAX];
int i;
printf("请输入%d个整数:",MAX);
for (i=0;i<MAX;i++)
scanf("%d",&array[i]);
QuickSort(array,0,MAX-1);
printf("快速排序后:");
for (i=0;i<MAX;i++)
printf("%d ",array[i]);
printf("\n");
return 0;
}
四、实验验证与练习
1、设给定的排序码序列为（ 72， 73， 71， 23， 94， 16， 05， 68），请写出归并排序和快速排序过程中每趟排序的结果。
归并排序：
第一趟：（72 73）（23 71）（16 94）（05 68）
第二趟：（23 71 72 73）（05 16 68 94）
第三趟：（05 16 23 68 71 72 73 94）
快速排序：
第一趟：设72为支点（68 05 71 23 16） 72 （94 73）
第二趟：设68为支点（16 05 23）68（71），设94为支点（73）94
第三趟：设16为支点（05）16（23）
得到有序序列：（05 16 23 68 71 72 73 94）结束
2、已知关键字集合（12,2,16,30,8,28,4,10,20,6,18)，用快速排序从小到大排序（选第一个记录为基准进行划分），写出第一趟排序结束时的序列。
（6 2 10 4 8）12（28 30 20 16 18）
思考题：
1、对序列（ 15， 9， 7， 8， 20， -1， 4）进行排序，进行一趟排序后，数据的排列变为（ 4， 9， 7， 8， -1， 15， 20），则采用的是（B ）排序。
A.选择排序 B.快速排序 C.希尔排序 D.冒泡排序
2、设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素， 最后选用（ C）排序法。
A.冒泡排序 B.快速排序 C.堆排序 D.直接插入排序
五、实验说明：
请同学们每次实验记得签到，把每次上机的内容保存好，将所有的实验内容压缩为：学号+班级+姓名+课程名，每次实验后由班长或学习委员统一收取，发送到：35578626@邮箱。