数据结构：实验八：数据排序

一、    实验目的

（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.实验结果截图

如需源文件，请私信作者，无偿