插入排序

#include<iostream>
using namespace std;
void insertsort(int a[],int n){
	int i,j,tmp;
	for(int i=1;i<n;i++){
		tmp=a[i];
		for(j=i;j>0&&a[j-1]>tmp;j--)
		a[j]=a[j-1];
		a[j]=tmp;
}}
int main(){
	int a[10]={2,3,5,1,4,8,6,9,7,0};
	insertsort(a,10);
	for(int i=0;i<10;i++)
	cout<<a[i]<<" ";
}

#include "seqlist.cpp"
void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序
{	int i, j; RecType tmp;
	for (i=1;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]
		}
		printf("  i=%d: ",i); DispList(R,n);
	}
}
 
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={9,8,7,6,5,4,3,2,1,0};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	InsertSort(R,n);
	printf("排序后:"); DispList(R,n);
	return 1;
}

#include "seqlist.cpp"
 
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
			for (j=i-1;j>=high+1;j--)	//集中进行元素后移
				R[j+1]=R[j];
			R[high+1]=tmp;				//插入tmp 
		}
		printf("  i=%d: ",i);
		DispList(R,n);
	} 
}
 
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={9,8,7,6,5,4,3,2,1,0};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	BinInsertSort(R,n);
	printf("排序后:"); DispList(R,n);
	return 1;
}

//Shell排序算法
#include "seqlist.cpp"
 
void ShellSort(RecType R[],int n) //希尔排序算法
{	int i,j,d;
	RecType tmp;
	d=n/2;					//增量置初值
	while (d>0)
	{	for (i=d;i<n;i++) 	//对所有组采用直接插入排序
		{	tmp=R[i];		//对相隔d个位置一组采用直接插入排序
			j=i-d;
			while (j>=0 && tmp.key<R[j].key)
			{	R[j+d]=R[j];
				j=j-d;
			}
			R[j+d]=tmp;
		}
		printf("  d=%d: ",d); DispList(R,n);
		d=d/2;				//减小增量
	}
}
int main()
{
	int n=10;
	RecType R[MAXL];
	KeyType a[]={9,8,7,6,5,4,3,2,1,0};
	CreateList(R,a,n);
	printf("排序前:"); DispList(R,n);
	ShellSort(R,n); 
	printf("排序后:"); DispList(R,n);
	return 1;
}