数据结构排序算法

#include<stdio.h>
typedef int InfoType; //定义其它数据项的类型
#include"c10-1.h"
int Partition(SqList &L,int low,int high)
{ //交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其
//所在位置，此时在它之前（后）的记录均不大（小）于它。算法10.6(b)
福州大学数计学院
《数据结构》上机实验报告
学号
姓名
班级
实验名称
排序算法
实验内容
常用排序算法的实现
实
验
目
的
和
要
求
熟悉并掌握各种排序算法的思想方法和实现该算法的基本技术
问
题
描
述
和
主
要
步
骤
实验内容：从键盘输入一组关键字序列分别实现下列排序:
1.实现简单选择排序、直接插入排序和冒泡排序。
2.实现快速排序算法。3.实现折半插入排序。4.采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。
printf("\n");
}
void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序后:\n");
print(d,N);
}
（4）快速排序
// algo10-6.cpp调用算法10.6(b)的程序(算法10.6(a)的改进)
#include"c1.h"
#definLeabharlann N 8void bubble_sort(int a[],int n)
{ //将a中整数序列重新排列成自小至大有序的整数序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
实验要点及说明：
一趟快速排序的具体做法是设置两个指针low和high,设立支点记录的关键字pivotkey，首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和支点记录互换，然后从low所指向的记录向后搜索，找到第一个关键字大于pivotkey的记录和支点记录互换，重复这两个步骤直到low=high。
--high;
L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端
while(low<high&&L.r[low].key<=pivotkey)
++low;
L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端
}
L.r[low]=L.r[0]; //枢轴记录到位
KeyType pivotkey;
L.r[0]=L.r[low]; //用子表的第一个记录作枢轴记录
pivotkey=L.r[low].key; //枢轴记录关键字
while(low< high)
{ //从表的两端交替地向中间扫描
while(low<high&&L.r[high].key>=pivotkey)
print(l);
SelectSort(l);
printf("排序后:\n");
print(l);
}
（2）直接插入排序和折半插入排序
#include"c1.h"
typedef int InfoType; //定义其它数据项的类型
#include"c9.h"
#include"c10-1.h"
#include"bo10-1.cpp"
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
{
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",r[i]);
print(l1);
BInsertSort(l2);
printf("折半插入排序后:\n");
print(l2);
P2_InsertSort(l3);
printf("2_路插入排序后:\n");
print(l3);
}
（3）冒泡排序
// algo10-4.cpp调用起泡排序(在教科书1.4.3算法效率的度量中)的程序
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
KeyType min;
int j,k;
k=i; //设第i个为最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) //找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList &L)
return low; //返回枢轴位置
}
#include"bo10-2.cpp"
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
实
验
结
果
（
截
图
表
示
）
（1）简单选择排序
// algo10-7.cpp简单选择排序
#include<stdio.h>
typedef int InfoType; //定义其它数据项的类型
#include"c10-1.h"
int SelectMinKey(SqList L,int i)
{ //返回在L.r[i..L.length]中key最小的记录的序号
SqList l1,l2,l3;
int i;
for(i=0;i<N;i++) //给l1.r赋值
l1.r[i+1]=d[i];
l1.length=N;
l2=l3=l1; //复制顺序表l2、l3与l1相同
printf("排序前:\n");
print(l1);
InsertSort(l1);
printf("直接插入排序后:\n");
{ //对顺序表L作简单选择排序。算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ //选择第i小的记录，并交换到位
j=SelectMinKey(L,i); //在L.r[i..L.length]中选择key最小的记录
if(i!=j)
{ //与第i个记录交换
void print(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
QuickSort(l);
printf("排序后:\n");
print(l);
}
研
究
与
探
讨
快速排序的平均时间只需O(nlogn),就平均时间来看，快速排序最佳