sort.cpp

2008软件公司面试题:排序大全：简单选择排序、冒泡排序、选择排序、shell排序、快速排序、插入排序、堆排序(从小到大)、归并排序（利用递归）

//各种排序方法，对int类型从小到大排序

#include <iostream.h>

void swap(int *a,int *b)
{
	int temp=*a;
	*a=*b;
	*b=temp;
}


//1.简单选择排序：基本思想：每次都将当前元素与其后元素一一比较并交换
void exchangeSort(int a[],int n)
{
	for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j])
				swap(&a[i],&a[j]);
		}
}

//2.冒泡排序。existExchange=0表示不存在交换，=1表示存在交换
void bubbleSort(int a[],int n)
{
	int i,j,existExchange;
	for(i=0,existExchange=1;(existExchange==1)&&(i<n-1);i++)
	{
		existExchange=0;
		for(j=0;j<n-1-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(&a[j],&a[j+1]);
				existExchange=1;
			}
		}
	}
}

//3.选择排序,减少赋值次数
void selectSort(int a[],int n)
{
	int i,j,k;
	for(i=0;i<n-1;i++)
	{
		k=i;
		for(j=k+1;j<n;j++)
			if(a[k]>a[j]) k=j;

		if(k!=i)
			swap(&a[i],&a[k]);
	}
}


//不正确的选择排序
/*
void selectSort(int a[],int n)
{
	int i,j,temp;
	for(i=0;i<n-1;i++)
	{
        temp=a[i]; 
		for(j=i+1;j<n;j++)
		{
			if(temp>a[j])
			{
				temp=a[j];
			}
		}
		if(a[i]!=temp)
			swap(&a[i],&temp);//就错在这里，应该交换数组中两个位置的元素，而非交换a[i]与temp，
		                      //这实际上相当于a[i]=temp
		for(int m=0;m<n;m++)
			cout<<a[m]<<" ";
	    cout<<endl;
	}

}
*/


//4.shell排序：每一趟都是一次希尔插入排序(shellPass()中用到交换)
void shellPass(int data[],int len,int increment)
{
	int i;
	for(i=0;i<len-increment;i++)
	{
		if(data[i]>data[i+increment])
			swap(&data[i],&data[i+increment]);
	}

	//输出提示
	cout<<"increment="<<increment<<":";
	for(i=0;i<len;i++)
		cout<<data[i]<<" ";
	cout<<endl;

}
void shellSort(int data[],int len)
{
	int increment=(len+1)/2;
	while(increment>1)
	{
		shellPass(data,len,increment);
		increment=(increment+1)/2;
	}
	if(increment==1)
		shellPass(data,len,increment);
}


//5.快速排序
//分割
int partition(int a[],int l,int h)
{
	int i=l,j=h,pivot=a[i];
	while(i<j)
	{
		while(i<j && pivot<=a[j])
			j--;
		if(i<j)
			a[i++]=a[j];
		while(i<j && pivot>=a[i])
			i++;
		if(i<j)
			a[j--]=a[i];
	}
	a[i]=pivot;

	cout<<"pivot:"<<pivot<<": ";
	for(int ii=l;ii<=h;ii++)
		cout<<a[ii]<<" ";
	cout<<endl;

	return i;
}
//递归调用
void quickSort(int a[],int low,int high)
{
	int pivotpos;
	if(low<high)
	{
		pivotpos=partition(a,low,high);
		quickSort(a,low,pivotpos-1);
		quickSort(a,pivotpos+1,high);
	}
}



//6.插入排序(用到交换)
void insertSort(int a[],int len)
{
	int i,j;
	for(i=1;i<len;i++)
	{
		for(j=i;j>0;j--)
		{
			if(a[j]<a[j-1])
				swap(&a[j],&a[j-1]);
		}
		cout<<i<<" times:";
		for(int k=0;k<len;k++)
			cout<<a[k]<<" ";
		cout<<endl;
	}
}


//7.插入排序(不交换),比用交换的方法  减少了  赋值的次数
void insertSortNoExchange(int a[],int len)
{
	int i,j,temp;
	for(i=1;i<len;i++)
	{
		if(a[i]<a[i-1])
		{
			temp=a[i];
			j=i-1;
			while(j>=0 && temp<a[j])
			{
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=temp;
		}
	}
}


//8.shell排序(不用交换)
void shellPassNoExchange(int a[],int len,int increment)
{
	int i,j,temp;
	for(i=0;i<len-increment;i++)
	{
		if(a[i+increment]<a[i])
		{
			temp=a[i+increment];
			j=i;
			while(j>=0 && temp<a[j])
			{
				a[j+increment]=a[j];
				j=j-increment;
			}
			a[j+increment]=temp;
		}
	}
	cout<<"increment="<<increment<<":";
	for(i=0;i<len;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}
void shellSortNoExchange(int a[],int len)
{
	int increment=(len+1)/2;
	while(increment>1)
	{
		shellPassNoExchange(a,len,increment);
		increment=(increment+1)/2;
	}
	if(increment==1)
		shellPassNoExchange(a,len,increment);
}



//9.堆排序(从小到大)
void heapAdjust(int a[],int s,int m)
{
	int j;
	int temp=a[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m && a[j]<a[j+1]) j++;
		if(temp>a[j]) break;
		a[s]=a[j];
		s=j;
	}
	a[s]=temp;
}
void heapSort(int a[],int n)
{
	int i;

	int *b=new int[n+1];
	for(i=0;i<n;i++)
		b[i+1]=a[i];

	for(i=n/2;i>0;i--)
	{
		heapAdjust(b,i,n);
		for(int k=1;k<=n;k++)
			cout<<b[k]<<" ";
		cout<<endl;
	}
	cout<<"................................................................................"<<endl;
	for(i=n;i>1;i--)
	{
		swap(&b[1],&b[i]);
		heapAdjust(b,1,i-1);
		for(int k=1;k<=n;k++)
			cout<<b[k]<<" ";
		cout<<endl;
	}

	for(i=0;i<n;i++)
		a[i]=b[i+1];
	delete [] b;
	cout<<"................................................................................"<<endl;
}



//10.归并排序（利用递归）
void merge(int sr[],int tr[],int i,int m,int n)
{
	int j,k;
	for(j=m+1,k=i;i<=m&&j<=n;k++)
	{
		if(sr[i]<sr[j]) tr[k]=sr[i++];
		else tr[k]=sr[j++];
	}
	if(i<=m)
	{
		for(;i<=m;i++,k++)
			tr[k]=sr[i];
	}
	if(j<=n)
	{
		for(;j<=n;j++,k++)
			tr[k]=sr[j];
	}
	//cout<<"merge()"<<endl;
}
void mSort(int sr[],int tr1[],int s,int t)
{

	
	int m;
//	int tr2[10];
	int *tr2=new int[t-s+1];
	cout<<"1 time of new"<<endl;
	if(s==t) tr1[s]=sr[s];
	else
	{
		
		m=(s+t)/2;
		//cout<<"m="<<m<<endl;
		mSort(sr,tr2,s,m);
		mSort(sr,tr2,m+1,t);
		merge(tr2,tr1,s,m,t);
	}
	//delete [] tr2;    //注意：此处不能delete，那么应该在哪里delete呢？
}
void mergeSort(int a[],int n)
{
//	int *temp=new int[n];
	mSort(a,a,0,n-1);
//	delete [] temp;
}









void printArray(int a[],int n)
{
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}



void main()
{
	int a[10]={4,1,8,10,5,9,7,6,3,2};
	printArray(a,10);
	mergeSort(a,10);
	printArray(a,10);
}