一、 实验目的
（1）掌握各种排序算法的过程和算法设计。
（2）体会各种排序算法的性能。
二、 实验要求
编写程序分别采用直接插入排序算法 、折半插入排序算法、冒泡排序算法、快速排序算法，实现对任意一组整型数据（无序），分别输出各一趟的排序结果。
三、实验环境
Windows+DEV C++( 或者其他编译工具)
四、实验步骤及结果
1.类型声明
typedef int ElemType;
typedef struct {
ElemType key;
} RecType;//排序元素的类型2.各类排序算法的实现
//直接插入排序
void InsertSort(RecType R[],int n) {//对R[0..n-1]按递增有序进行直接插入排序
RecType tmp;
int i,j;
for(i=0; i<n; i++) {
if(R[i].key<R[i-1].key) {//反序时
tmp=R[i];
j=i-1;
do {//找R[i]的插入位置
R[j+1]=R[j];//将关键字大于R[i].key的记录后移
j--;
} while(j>=0&&R[j].key>tmp.key);
R[j+1]=tmp;//在j+1处插入R[i]
}
}
}//折半插入排序
void BinInsertSort(RecType R[],int n) {
int i,j,low,high,mid;
RecType tmp;
for(i=1; i<n; i++) {
if(R[i].key<R[i-1].key) {//反序时
tmp=R[i];//将R[i]保存到tmp中
low=0;
high=i-1;
while(low<=high) {//在R[low..high]中查找插入的位置
mid=(low+high)/2;//取中间位置
if(tmp.key<R[mid].key)
high=mid-1;//插入点在左半区
else
low=mid+1;//插入点在右半区
}//找位置high+1
for(j=i-1; j>=high+1; j--)//集中进行元素的后移
R[j+1]=R[j];
R[high+1]=tmp;//插入tmp
}
}
}//冒泡排序
void BubbleSort(RecType R[],int n) {
int i,j;
for(i=0; i<n-1; i++)
for(j=n-1; j>i; j--)//将R[i]元素归位
if(R[j].key<R[j-1].key) //相邻的两个元素反序时
swap(R[j],R[j-1]);//将R[j]和R[j-1]两个元素交换
}//快速排序
int partition(RecType R[],int s,int t) {//一趟划分
int i=s,j=t;
RecType base=R[i];//以R[i]为基准
while(i<j) {//从两端交替向中间扫描，直到i=j为止
while(j>i&&R[j].key>=base.key)
j--;//从右往左遍历，找一个小于base.key的R[j]
if(i<j) {
R[i]=R[j];
i++;
}
while(i<j&&R[i].key<=base.key)
i++;//从左往右遍历，找一个大于base.key的R[i]
if(i<j) {
R[i]=R[j];
j--;
}
}
R[i]=base;
return i;
}
void QuickSort(RecType R[],int s,int t) {//对R[s..t]中的元素进行快速排序
int i;
if(s<t) {//区间内至少存在两个元素的情况
i=partition(R,s,t);
QuickSort(R,s,i-1);//对左区间递归排序
QuickSort(R,i+1,t);//对右区间递归排序
}
}3.主程序设计及完成实验要求中的功能
//输出
void Display(RecType R[],int n) {
for(int i=0; i<n; i++)
cout<<R[i].key<<" ";
cout<<endl;
}
//主面板
void Interface() {
cout<<"0.退出程序"<<endl;
cout<<"1.直接插入排序算法"<<endl;
cout<<"2.折半插入排序算法"<<endl;
cout<<"3.冒泡排序算法"<<endl;
cout<<"4.快速排序算法"<<endl;
cout << "请输入选择：";
}
//选择匹配面板
void Select(RecType R[],int n,int x) {
switch(x) {
case 0:
cout << "已退出程序！";
exit(0);
case 1:
InsertSort(R,n);
Display(R,n);
break;
case 2:
BinInsertSort(R,n);
Display(R,n);
break;
case 3:
BubbleSort(R,n);
Display(R,n);
break;
case 4:
QuickSort(R,1,n-1);
Display(R,n);
break;
};
}
int main() {
int n=0,x;
RecType R[N]= {5,8,6,10,1,4,9,7,3,2};
for(int i=0; i<N&&R[i].key!=0; i++)
n++;
cout<<"初始序列为："<<endl;
Display(R,n);
cout<<endl;
while(1) {
Interface();
cin>>x;
while(!(x==0||x==1||x==2||x==3||x==4)) {
system("cls");
cout<<"输入错误请重新输入！"<<endl;
Interface();
cin>>x;
}
Select(R,n,x);
}
}完整代码：
#include<iostream>
using namespace std;
#define N 100
typedef int ElemType;
typedef struct {
ElemType key;
} RecType;//排序元素的类型
//直接插入排序
void InsertSort(RecType R[],int n) {//对R[0..n-1]按递增有序进行直接插入排序
RecType tmp;
int i,j;
for(i=0; i<n; i++) {
if(R[i].key<R[i-1].key) {//反序时
tmp=R[i];
j=i-1;
do {//找R[i]的插入位置
R[j+1]=R[j];//将关键字大于R[i].key的记录后移
j--;
} while(j>=0&&R[j].key>tmp.key);
R[j+1]=tmp;//在j+1处插入R[i]
}
}
}
//折半插入排序
void BinInsertSort(RecType R[],int n) {
int i,j,low,high,mid;
RecType tmp;
for(i=1; i<n; i++) {
if(R[i].key<R[i-1].key) {//反序时
tmp=R[i];//将R[i]保存到tmp中
low=0;
high=i-1;
while(low<=high) {//在R[low..high]中查找插入的位置
mid=(low+high)/2;//取中间位置
if(tmp.key<R[mid].key)
high=mid-1;//插入点在左半区
else
low=mid+1;//插入点在右半区
}//找位置high+1
for(j=i-1; j>=high+1; j--)//集中进行元素的后移
R[j+1]=R[j];
R[high+1]=tmp;//插入tmp
}
}
}
//冒泡排序
void BubbleSort(RecType R[],int n) {
int i,j;
for(i=0; i<n-1; i++)
for(j=n-1; j>i; j--)//将R[i]元素归位
if(R[j].key<R[j-1].key) //相邻的两个元素反序时
swap(R[j],R[j-1]);//将R[j]和R[j-1]两个元素交换
}
//快速排序
int partition(RecType R[],int s,int t) {//一趟划分
int i=s,j=t;
RecType base=R[i];//以R[i]为基准
while(i<j) {//从两端交替向中间扫描，直到i=j为止
while(j>i&&R[j].key>=base.key)
j--;//从右往左遍历，找一个小于base.key的R[j]
if(i<j) {
R[i]=R[j];
i++;
}
while(i<j&&R[i].key<=base.key)
i++;//从左往右遍历，找一个大于base.key的R[i]
if(i<j) {
R[i]=R[j];
j--;
}
}
R[i]=base;
return i;
}
void QuickSort(RecType R[],int s,int t) {//对R[s..t]中的元素进行快速排序
int i;
if(s<t) {//区间内至少存在两个元素的情况
i=partition(R,s,t);
QuickSort(R,s,i-1);//对左区间递归排序
QuickSort(R,i+1,t);//对右区间递归排序
}
}
//输出
void Display(RecType R[],int n) {
for(int i=0; i<n; i++)
cout<<R[i].key<<" ";
cout<<endl;
}
//主面板
void Interface() {
cout<<"0.退出程序"<<endl;
cout<<"1.直接插入排序算法"<<endl;
cout<<"2.折半插入排序算法"<<endl;
cout<<"3.冒泡排序算法"<<endl;
cout<<"4.快速排序算法"<<endl;
cout << "请输入选择：";
}
//选择匹配面板
void Select(RecType R[],int n,int x) {
switch(x) {
case 0:
cout << "已退出程序！";
exit(0);
case 1:
InsertSort(R,n);
Display(R,n);
break;
case 2:
BinInsertSort(R,n);
Display(R,n);
break;
case 3:
BubbleSort(R,n);
Display(R,n);
break;
case 4:
QuickSort(R,1,n-1);
Display(R,n);
break;
};
}
int main() {
int n=0,x;
RecType R[N]={28,16,32,12,60,2,5,72};
//RecType R[N]= {5,8,6,10,1,4,9,7,3,2};
for(int i=0; i<N&&R[i].key!=0; i++)
n++;
cout<<"初始序列为："<<endl;
Display(R,n);
cout<<endl;
while(1) {
Interface();
cin>>x;
while(!(x==0||x==1||x==2||x==3||x==4)) {
system("cls");
cout<<"输入错误请重新输入！"<<endl;
Interface();
cin>>x;
}
Select(R,n,x);
}
}
4.实验结果截图
如需源文件，请私信作者，无偿