sort .cpp

各种排序算法

#include <iostream.h>
int SIZE=6;
int main()
{
	void insertsort(int R[],int n);//插入排序
	void Bubblesort(int R[],int n);//冒泡排序
	void ShellSort (int Vector[], int arrSize );//希尔排序
	void QuickSort(int Array[], int low, int high);//快排序
	void merge(int A[], int Alen, int B[], int Blen, int C[]);//并归排序
	void selsort(int number[],int n);//选择排序
	void bucketSort( int a[] ,int SIZE);//基数排序
	int a[6]={9,2,8,4,5,6},b[6]={9,2,8,4,5,6},c[6]={9,2,8,4,5,6},d[6]={9,2,8,4,5,6},e[6]={97,2,867,43,57,63},f[6]={9,2,8,4,5,6};
	int g[5]={7,8,5,0,4};
	int h[11];
//=======================================================================================
	cout<<"insertsort(a,6)test:";
	insertsort(a,6);
	for(int i=0;i<6;i++)
		cout<<a[i]<<" ";
	cout<<endl;
//========================================================================================
	cout<<"Bubblesort(b,6)test:";
	Bubblesort(b,6);
	for(i=0;i<6;i++)
		cout<<b[i]<<" ";
	cout<<endl;
//========================================================================================
	cout<<"ShellSort(c,6)test:";
	ShellSort(c,6);
	for(i=0;i<6;i++)
		cout<<c[i]<<" ";
	cout<<endl;
//==========================================================================================
	cout<<"QuickSort(g,0,5)test:";
	QuickSort(g,0,5);
	for(i=0;i<5;i++)
		cout<<g[i]<<" ";
	cout<<endl;
//===========================================================================================
	cout<<"merge(a,6,g,5,h)test:";
	merge(a,6,b,5,h);
	for(i=0;i<11;i++)
		cout<<h[i]<<" ";
	cout<<endl;
//============================================================================================
	cout<<"selsort(d,6)test:";
	selsort(d,6);
	for(i=0;i<6;i++)
		cout<<d[i]<<" ";
	cout<<endl;
//==============================================================================================
	cout<<"bucketSort(e,6)test:";
	bucketSort(e,6);
	for(i=0;i<6;i++)
		cout<<e[i]<<" ";
	cout<<endl;
	return 0;
}
void insertsort(int R[],int n)
//待排序元素用一个数组R表示，数组有n个元素
{
	for ( int i=1; i<n; i++)   //i表示插入次数，共进行n-1次插入
	{ 
		int temp=R[i]; //把待排序元素赋给temp
		int j=i-1; 
		while ((j>=0)&& (temp<R[j]))
		{      
			R[j+1]=R[j]; j--; 
		} // 顺序比较和移动
		R[j+1]=temp;}
}
void Bubblesort(int R[],int n)
{  
	int flag=1;  //当flag为0则停止排序
	for(int i=1; i<n; i++)
	{  //i表示趟数，最多n-1趟
		flag=0;//开始时元素未交换
		for (int j=n-1; j>=i; j--)  
			if (R[j]<R[j-1])	  
			{ //发生逆序   
				int  t=R[j];
				R[j]=R[j-1];
				R[j-1]=t;
				flag=1; 
			} //交换，并标记发生了交换
          if(flag==0)
			  return;     
	}
}    

void ShellSort (int Vector[], int arrSize  )
{
    int temp;
    int gap = arrSize / 2;  //gap是子序列间隔	
    while ( gap != 0 ) 
	{	          //循环,直到gap为零
        for ( int i = gap; i < arrSize; i++) 
		{
            temp = Vector[i];	//直接插入排序
            for ( int j = i; j >= gap; j -= gap )
                if ( temp < Vector[j-gap] )
                    Vector[j] = Vector[j-gap];
                else break;          
              Vector[j] = temp;
        }				
        gap = ( int ) ( gap / 2 );
    }
}
void QuickSort(int Array[], int low, int high)
{
	int Partition(int Array[], int low, int high);
	int PivotLocation;
  	if(low < high)
	{
		PivotLocation = Partition(Array, low, high);
		QuickSort(Array, low, PivotLocation-1);//左边
		QuickSort(Array, PivotLocation+1, high);//右边
  	}
}

int Partition(int Array[], int low, int high)
{
   int pivot = Array[low];
   while(low < high)
   {  
	   while(low < high && Array[high] >= pivot)
		   high --;
	   Array[low] = Array[high];
	   while(low < high && Array[low] <= pivot)	
		   low++;
	   Array[high] = Array[low];
    }  
    Array[low] = pivot;
    return low;
}
void merge(int A[], int Alen, int B[], int Blen, int C[])
{
      int i=0,j=0,k=0;
      while(i < Alen && j < Blen)
	  {
		  if(A[i] <= B[j])
			  C[k++] = A[i++]; 
	       else
			   C[k++] = B[j++];
	  }
	  while(i < Alen)
		  C[k++] = A[i++];
	  while(j < Blen)
		  C[k++] = B[j++];
}
void selsort(int number[],int n)
{
	int i, j, m;
	for(i = 0; i < n-1; i++) 
	{ 
		m = i; 
		for(j = i+1; j < n; j++) 
			if(number[j] < number[m]) m = j; 
			if( i != m)
			{
				int temp;
				temp=number[i];
				number[i]=number[m];
				number[m]=temp;
			} 
	}
}

void bucketSort( int a[] ,int SIZE)
{
	int totalDigits, bucket[ 10 ][ 6] = { 0 };
///////////查找到数组中最大的数，并确定对多需要模10的次数/////////////////////
	int largest = a[ 0 ], digits = 0;
	for ( int i = 1; i < SIZE; ++i )
		if ( a[ i ] > largest )
			largest = a[i];
		while ( largest != 0 )
		{
			++digits;
			largest /= 10;
		}
//////////////////////////////////////////////////////////////////////////////		 
	totalDigits =digits;
	for (i = 1; i <= totalDigits; ++i )
	{
		int divisor = 10, bucketNumber, elementNumber;
		for ( int m = 1; m < totalDigits; ++m ) 
		{	
			divisor *= 10; 
////////////////////把a[]进行拆分并与b[][]对应并对排序///////////////////////////////////////////////////////////////
			for ( int k = 0; k < SIZE; ++k )
			{ 
				bucketNumber = ( a[ k ] % divisor - a[ k ] %( divisor / 10 ) ) / ( divisor / 10 );
				elementNumber = ++bucket[ bucketNumber ][ 0 ];
				bucket[ bucketNumber ][ elementNumber ] = a[ k ];
			}

			int subscript = 0;
			for (i = 0; i < 10; ++i )
				for ( int j = 1; j <= bucket[ i ][ 0 ]; ++j )
					a[ subscript++ ] = bucket[ i ][ j ];
				if ( i != totalDigits )
					for ( int i = 0; i < 10; ++i )
						for ( int j = 0; j < SIZE; ++j )
							bucket[ i ][ j ] = 0;
			}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		}
}