sortcompare.cpp

排序算法比较:直接插入排序、折半插入排序

#include<stdio.h>
#include<stdlib.h>
#include"iostream.h"

#define M 11


/********************************************/
/*               插入排序法                 */
/********************************************/
void InsertSort(int a[])
	{
		int i, j;

		for(i=2; i<M; i++)
		{
			if(a[i]<a[i-1])
			{
				a[0]=a[i];						//a[0]作为哨兵
				a[i]=a[i-1];
				j=i-1;
				while(a[--j]>a[0])
				{
					a[j+1]=a[j];
				}
				a[j+1]=a[0];
			}
		}
  
}//InsertSort


/********************************************/
/*               折半排序法                 */
/********************************************/
void BinarySort(int a[])
{
	int i, j, m, low, high;

		for (i=2; i<M; i++)
		{
			a[0]=a[i];
			low=1;
			high=i-1;
			while (low<=high)					//找到i的位置,用low和high指向它
			{
				m=(low+high)/2;
				if(a[0]>a[m])
				{
					low=m+1;
				}
				else
				{
					high=m-1;
				}
			}
			for(j=i-1; j>high; j--)
				{
					a[j+1]=a[j];
				}
				a[j+1]=a[0];
		}
 
}//BinarySort


/********************************************/
/*              冒泡排序法                  */
/********************************************/
void Bubble(int a[])//
{
	int i, j, temp;
	int flag = 1;

	for(i=1; i<=10; i++)
	{
		for(j=i+1; j<=10; j++)
		{
			if(a[i]>a[j])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
 
}//Bubble


/********************************************/
/*               快速排序法                 */
/********************************************/
int Parttion(int a[],int low,int high)				//快速排序的一趟
{
	a[0]=a[low];									//作为枢轴
	while(low<high)
	{
		while( low<high && a[high]>=a[0] )	--high;
		a[low]=a[high];								//将比枢轴小的记录移到低端
		while( low<high && a[low]<=a[0] ) ++low;
		a[high]=a[low];								//将比枢轴大的记录移到高端
	}
	a[low]=a[0];
	return low;
}

void QuickSort(int a[],int low,int high)
{
	int pivotloc;						//pivotloc为枢轴
	if(low<high){
		pivotloc=Parttion(a,low,high);				//将a[]一分为二
		QuickSort(a,low,pivotloc-1);				//对低子表递归排序
		QuickSort(a,pivotloc+1,high);				//对高子表递归排序
	}
 
}



/********************************************/
/*				 选择排序法                 */
/********************************************/
void SelectSort(int a[])
{
   int pos;											//目前最小的数字的位置     
   int i,j,temp;									//temp存最小数字

   for(i=1; i<M; ++i)
   {
      pos=i;
      temp=a[i];
      for(j=i+1; j<M; j++)							//查找最小的字符
		  if(a[j]<temp)
          {
            pos=j;									//新的最小字符的位置
            temp=a[j];
		  }
      a[pos]=a[i];									//交换位置
      a[i]=temp;
   }

}


/********************************************/
/*			  	  堆排序法                  */
/********************************************/
void HeapAdjust(int a[], int i, int n)				//将a[i],a[2*i],a[2*i+1]进行调整	
{
	int j, flag=1, temp;
	j=2*i;
	temp=a[i];

	while(j<=n && flag)
	{
		if(j<n && a[j]<a[j+1]) j++;					//选出左右孩子中较大的
		if(temp>=a[j]) flag=0;						//如果根结点最大,则比较结束,直接选出根结点
		else										//根结点与大孩子交换后,仍需与子树继续比较
		{
			a[j/2]=a[j];
			j*=2;
		}
	}
	a[j/2]=temp;
}

void HeapSort(int a[])
{
	int i;
	for(i=(M-1)/2; i>0; i--)HeapAdjust(a, i, M-1);	//用循环建大顶堆
	i=M-1;
	while(i>0)
	{
		a[0]=a[i];									//寄存a[i]到a[0]
		a[i]=a[1];									//最大值存到a[i]
		a[1]=a[0];									//将a[0](即原来的a[i])存到a[1]
		i--;
		HeapAdjust(a, 1, i);
	}
	
}

/********************************************/
/*				 基数排序法                 */
/********************************************/
void Distribute(int a[],int const i,int keynum[],int s[M][M])
//一趟分配 
{
	int j=i, key, p=1;

	while(--j)
	{
		p*=10;
	}
	cout<<p<<endl;
	for( j=1; j<M; j++)
	{
		a[0]=a[j]/p; 
		key=((a[0])%10); 
		++keynum[key];
		s[key][keynum[key]]=a[j];
	}
	cout<<endl;
	for( j=0; j<M-1; j++)cout<<keynum[j]; 
	
}

void Collect(int a[],int keynum[],int s[M-1][M])		
//一趟收集,按关键字从小到大排序
{
	int j, p, k=1,q=0; 

	for( j=0; j<M-1; j++)
	{
		p=0;
		while(++p<=keynum[j])
		{
			a[k]=s[j][p];
			++k;
		}//while
	}//for 
}	

void RadixSort(int a[])
{
	int i;						

	for( i=1; i<=3; i++)								//共进行3趟
	{
		int keynum[M-1]={0}, s[M-1][M]={0};				//keynum[0..9]分别表示关键字为0..9的数的个数
		Distribute( a, i, keynum, s);
		Collect( a, keynum, s);
	}
 
}


/********************************************/
/*				 希尔排序法                 */
/********************************************/
void ShellSort(int a[])
{
	int i,j,temp,k;
 
	for( k=M-1/2; k>0; k--)		//k作为每次比较的跨度,并随次数的增减而递减
	{
		for(i=k+1; i<=10; i++)		//把最小的数放到a[k]上
		{
			j=i-k;
			while(j>0)				
			{
				if(a[j]>a[i])
				{
					temp=a[j];
					a[j]=a[i];
					a[i]=temp;
				}
				j-=k;
			}
		}
	}
 
}





void main(void)
{
	int i, a[M]={ 0, 209, 386, 768, 185, 247, 606, 230, 834, 54, 12};
	char select;
	printf("排序之前的元素为:");
	for( i=1; i<M; i++)
	{
		printf("%4d",a[i]);
	}

	printf("\n");
	printf("1: 进行直接插入排序\n");
	printf("2: 进行折半插入排序\n");
	printf("3: 进行冒泡排序\n");
	printf("4: 进行快速排序\n");
	printf("5: 进行选择排序\n");
	printf("6: 进行堆排序\n");
	printf("7: 进行基数排序\n");
	printf("8: 进行希尔排序\n");
	printf("请选择:");
	cin>>select;
	while(select<'1'||select>'8')
	{
		printf("输入错误,请重新输入:");
		cin>>select;
	}


	switch(select)
	{
		case '1':
			printf("进行插入排序:");
			InsertSort(a);
			break;
		case '2':
			printf("进行折半排序:");
			BinarySort(a);
			break;
		case '3':
			printf("进行冒泡排序:");
			Bubble(a);
			break;
		case '4':
			printf("进行快速排序:");
			QuickSort(a, 1, M-1);
			break;
		case '5':
			printf("进行选择排序:");
			SelectSort(a);
			break;
		case '6':
			printf("进行堆排序:");
			HeapSort(a);
			break;
		case '7':
			printf("进行基数排序:");
			RadixSort(a);
			break;
		case '8':
			printf("进行希尔排序:");
			ShellSort(a);
			break;
		default:
			break;
	}
	cout<<"排序结果为:\n";

	for(i=1; i<M; i++)
	{
		printf("%4d",a[i]);
	}
	printf("\n");

	system("pause");
}