各种排序算法

[c++]代码库

#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef int InfoType;
typedef struct
{
	KeyType key;
	InfoType otherinfo;
} RedType;
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
} SqList;

void InsertSort ( SqList *L )
{
	int i,j;
	for ( i=2; i<=L->length; ++i )
		if ( LT ( L->r[i].key,L->r[i-1].key ) )
		{
			L->r[0]=L->r[i];
			for ( j=i-1; LT ( L->r[0].key,L->r[j].key ); --j )
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0];
		}
}

void BInsertSort ( SqList *L )
{
	int i,j;
	int low,high,m;
	for ( i=2; i<=L->length; ++i )
	{
		L->r[0]=L->r[i];
		low=1;
		high=i-1;
		while ( low<=high )
		{
			m= ( low+high ) /2;
			if ( LT ( L->r[0].key,L->r[m].key ) )
				high=m-1;
			else low=m+1;
		}
		for ( j=i-1; j>=high+1; --j )
			L->r[j+1]=L->r[j];
		L->r[high+1]=L->r[0];
	}
}

/* QuickSort related function */
int Partition ( SqList *L,int low,int high )
{
	int pivotkey;
	L->r[0]=L->r[low];
	pivotkey=L->r[low].key;
	while ( low<high )
	{
		while ( low<high&&L->r[high].key>=pivotkey ) --high;
		L->r[low]=L->r[high];
		while ( low<high&&L->r[low].key<=pivotkey ) ++low;
		L->r[high]=L->r[low];
	}
	L->r[low]=L->r[0];
	return low;
}
void QSort ( SqList *L,int low,int high )
{
	int pivotloc;
	if ( low<high )
	{
		pivotloc=Partition ( L,low,high );
		QSort ( L,low,pivotloc-1 );
		QSort ( L,pivotloc+1,high );
	}
}
void QuickSort ( SqList *L )
{
	QSort ( L,1,L->length );
}                    /* End QuickSort related function*/

/*SelectSort related function */
int SelectMinKey ( SqList L,int i )
{
	int k;
	int j;
	k=i;
	for ( j=i; j<L.length+1; j++ )
		if ( L.r[k].key>L.r[j].key )
			k=j;
	return k;
}
void SelectSort ( SqList *L )
{
	RedType t;
	int i,j;
	for ( i=1; i<L->length; ++i )
	{
		j=SelectMinKey ( *L,i );
		if ( i!=j )
		{
			t=L->r[i];
			L->r[i]=L->r[j];
			L->r[j]=t;
		}
	}
}           /*End SelectSort related function */


typedef SqList HeapType;
void HeapAdjust ( HeapType *H,int s,int m )
{
	RedType rc;
	int j;
	rc=H->r[s];
	for ( j=2*s; j<=m; j*=2 )
	{
		if ( j<m&&LT ( H->r[j].key,H->r[j+1].key ) ) ++j;
		if ( !LT ( rc.key,H->r[j].key ) ) break;
		H->r[s]=H->r[j];
		s=j;
	}
	H->r[s]=rc;
}
void HeapSort ( HeapType *H )
{
	RedType t;
	int i;
	for ( i=H->length/2; i>0; --i )
		HeapAdjust ( H,i,H->length );
	for ( i=H->length; i>1; --i )
	{
		t=H->r[1];
		H->r[1]=H->r[i];
		H->r[i]=t;
		HeapAdjust ( H,1,i-1 );
	}
}

main()
{
	int a[]={49,38,65,97,76,13,27,49};
	int i,k;
	SqList s;
	printf ( "\nThe record to be sort:\n" );
	for ( i=1; i<9; i++ )
	{
		s.r[i].key=a[i-1];
		printf ( "%d  ",a[i-1] );
	}
	s.length=i-1;
	printf ( "\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n" );
	printf ( "\t5,HeapSort\n\tPress 1..5 to select a function\n" );
	scanf ( "%d",&k );
	switch ( k )
	{
	case 1:
		InsertSort ( &s );
		break;
	case 2:
		BInsertSort ( &s );
		break;
	case 3:
		QuickSort ( &s );
		break;
	case 4:
		SelectSort ( &s );
		break;
	case 5:
		HeapSort ( &s );
		break;
	default:
		printf ( "No function which you select.\n" );
	}
	printf ( "\nThe records be sorted:\n" );
	for ( i=1; i<9; i++ )
		printf ( "%d  ",s.r[i].key );
	printf ( "\n\n\tPress any key to exit.\n" );
	getch();
}