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

一、 实验目的

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