typedef struct{  
       int key;   //假設(shè)關(guān)鍵字為int型
       OtherType  other_data;
} RecordType;

void InsSort(RecordType  r[],  int length)
/* 對(duì)記錄數(shù)組r做直接插入排序，length為數(shù)組中待排序記錄的數(shù)目*/
{ 
	int i,j;
	for (i=2;  i<=length;  i++) 
	{
		r[0]=r[i];      /*將待插入記錄存放到監(jiān)視哨r[0]中*/
		j=i-1;	         
		while (r[0].key< r[j].key )     /* 尋找插入位置 */
		{
			r[j+1]= r[j]; 
			j=j-1;
		}
		r[j+1]=r[0];	/*將待插入記錄插入到已排序的序列中*/
	}
} /*  InsSort  */ 

void BinSort (RecordType  r[],  int length)
/*對(duì)記錄數(shù)組r進(jìn)行折半插入排序，length為數(shù)組的長(zhǎng)度*/
{
	int i,j;
    RecordType x;	
    int low,high,mid;
	for (i=2; i<=length ; ++i ) 
	{
		x= r[i];  low=1;  high=i-1;
		while (low<=high )                  /* 確定插入位置*/ 
		{
			mid=(low+high) / 2;
			if ( x.key< r[mid].key) high=mid-1;
			else 	low=mid+1;
		}
		for ( j=i-1 ; j>= low; --j )   r[j+1]= r[j];    /*  記錄依次向后移動(dòng) */ 
		r[low]=x;   /* 插入記錄 */ 
	}
}/*BinSort*/

void  ShellInsert(RecordType r[], int length,  int  delta)
/*對(duì)記錄數(shù)組r做一趟希爾插入排序，length為數(shù)組的長(zhǎng)度,delta 為增量*/
{	int i,j;
	for(i=1+delta;i<= length; i++)     /* 1+delta為第一個(gè)子序列的第二個(gè)元素的下標(biāo) */
		if(r[i].key < r[i-delta].key)
		{
			r[0]= r[i];          /*  備份r[i]  (不做監(jiān)視哨) */
			for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)
				r[j+delta]= r[j];
				r[j+delta]= r[0];
		}
}/*ShellInsert*/

void  BubbleSort(RecordType r[], int length )
/*對(duì)記錄數(shù)組r做冒泡排序，length為數(shù)組的長(zhǎng)度*/
{	int n,i,j; nt change; RecordType x; n=length;  change=TRUE;
		for ( i=1 ; i<= n-1 && change ;++i ) 
		{	change=FALSE;
				for ( j=1 ; j<= n-i ; ++j) 
					if (r[j].key > r[j+1].key )  
					{
						x= r[j];
						r[j]= r[j+1];
						r[j+1]= x;
						change=TRUE;
					} 
		}
} /*  BubbleSort

void QKSort(RecordType r[],int low, int high )
/*對(duì)記錄數(shù)組r[low..high]用快速排序算法進(jìn)行排序*/
{
	int pos;
	if(low<high)
	{
		pos=QKPass(r, low, high);  /*調(diào)用一趟快速排序，將樞軸元素為界劃分兩個(gè)子表*/
		QKSort(r, low, pos-1);     /*對(duì)左部子表快速排序*/
		QKSort(r, pos+1, high); /*對(duì)右部子表快速排序*/
		
	}
}

int QKPass(RecordType r[],int left,int right)
/*對(duì)記錄數(shù)組r 中的r[left]至r[right]部分進(jìn)行一趟排序，并得到基準(zhǔn)的位置，使得排序后的結(jié)果滿足其之后（前）的記錄的關(guān)鍵字均不小于（大于）于基準(zhǔn)記錄*/
{ 
	RecordType x;	int low,high;
	x= r[left];             /* 選擇基準(zhǔn)記錄*/ 
	low=left;  	high=right;
	while ( low<high )
	{
		while (low< high && r[high].key>=x.key )   /* high從右到左找小于x.key的記錄 */
			high--;
		if ( low <high ) {r[low]= r[high];  low++;}  /* 找到小于x.key的記錄，則進(jìn)行交換*/
		while (low<high && r[low].key<x.key  )   /* low從左到右找大于x.key的記錄 */
			low++; 
		if (  low<high  ){ r[high]= r[low]; high--; } /* 找到大于x.key的記錄，則交換*/
	}
	r[low]=x;                     /*將基準(zhǔn)記錄保存到low=high的位置*/
	return low;                     /*返回基準(zhǔn)記錄的位置*/
} /* QKPass */