main.cpp

数据结构试验 实验一 线性表的顺序表示与实现 实验二 线性表的链式表示与实现 实验三 栈与队列及其应用 实验四 二叉树的应用 实验五 图的遍历与应用 实验六 查找技术 实验七 内部排序

#include <stdlib.h>
#include <ctime>
#include <iostream.h>
void disp(int a[],int low,int high)
{
int i;
for(i=low;i<=high;i++) cout<<a[i]<<"  ";
cout<<endl;
}

void InsertSortA(int a[ ],int n)
{
	for(int i=2;i<=n;i++)
		if(a[i]<a[i-1])
		{
			a[0]=a[i];
			a[i]=a[i-1];
		
		for(int j=i-2;a[0]<a[j];--j) a[j+1]=a[j];
		a[j+1]=a[0];
		}
}

void BinInsertSort(int a[ ], int n)
{
	for(int i=2;i<=n;i++)
	{
		a[0]=a[i];
		int low=1,high=i-1;
		while(low<=high)
		{
			int m=(low+high)/2;
			if(a[0]<a[m])high=m-1;
			else low=m+1;
		}
		for(int j=i-1;j>=high;--j)a[j+1]=a[j];
		a[high+1]=a[0];
	}
}


void BubbleSort(int a[ ], int n)
{
	for(int i=1;i<n;i++)
		for(int j=1;j<=n-i;j++)
			if(a[j]>a[j+1])
			{
				a[0]=a[j];
				a[j]=a[j+1];
				a[j+1]=a[0];
			}
}



int SelectMinkey(int a[],int n,int i)
{
	int k=i;
	for(int j=i+1;j<=n;j++)
		if(a[j]<a[k]) k=j;
		return k;
}
void SelectionSort(int a[ ], int n)
{
	for(int i=1;i<n;++i){
	int j=SelectMinkey(a,n,i);
	if(i!=j){a[0]=a[i];a[i]=a[j];a[j]=a[0];}
}
}
	

void main()
{
int a[6]={2,1,4,7,3,0},n=5;
cout<<"原始序列为:";
disp(a,1,n);
InsertSortA(a, n);
cout<<"直接插入排序序列:";
disp(a,1,n);
cout<<"折半插入排序序列:";
disp(a,1,n);
cout<<"起泡排序序列:";
disp(a,1,n);
SelectionSort(a,n);
cout<<"选择排序序列:";
disp(a,1,n);
}