sort.txt

常见的多种排序算法：插入排序 冒泡排序 快速排序 希尔排序 堆排序

#include<iostream>
#include<iomanip>
#include<string>
using namespace std;
const int MAX=100;
void InsertSort(int R[],int n);
void ShellSort(int R[],int n);
void BubbleSort(int R[],int n);
int PartitionQuick(int R[],int l,int h);
void QuickSort(int R[],int l,int h);

void InsertSort(int R[],int n)//插入排序
{ 
	
    int i,j;    
    for(i=n;i>=1;i--)
			R[i]=R[i-1];    
    for(i=2;i<=n;i++)
        if(R[i]<R[i-1])
		{
    	      R[0]=R[i];
			  j=i-1; 
              while(1)
				{      	
       			    R[j+1]=R[j]; 
					j--;     	 
                    if(R[0]>=R[j])
        	           break;
				}  
				R[j+1]=R[0]; 
		}
     for(i=0;i<n;i++)
			R[i]=R[i+1];
}

void ShellSort(int R[],int n)//希尔排序
{
	int i,j,k;	
	for(i=n;i>=1;i--)
		R[i]=R[i-1];
	k=n/2;
	while(k>=1)
	{
		for(i=k+1;i<=n;i++)
		{		
			R[0]=R[i];
			j=i-k;		
			while((R[j]>R[0])&&(j>=0))
			{			
				R[j+k]=R[j];			
				j=j-k;
			}		
			R[j+k]=R[0];
		}	
		k=k/2;
	}
	for(i=0;i<n;i++)
		R[i]=R[i+1];
}

void BubbleSort(int R[],int n)//冒泡排序
{ 	 
   int i,j;  
   int flag;    
	 for(i=n;i>=1;i--)
		 R[i]=R[i-1];
   for(i=1;i<n;i++)
   { 
       flag=0; 
       for(j=n-1;j>=i;j--)         
        if(R[j+1]<R[j])
        {        
          R[0]=R[j+1]; 
          R[j+1]=R[j];
          R[j]=R[0];          
          flag=1; 
        }      
       if(!flag) 
       {       	 
       	  for(i=0;i<n;i++)
				  	R[i]=R[i+1];
	        return;
	     }
     }
}

int PartitionQuick(int R[],int l,int h)//快速排序
{
	int i,j;
	int x;
	i=l;
	j=h;
	x=R[i];	
	while(i<j)
	{	
		while((i<j)&&(R[j]>=x))
			j--;		
		if(i<j)
		{			
			R[i]=R[j];
			i++;
		}	
		while((i<j)&&(R[i]<=x))
			i++;	
		if(i<j)
		{			
			R[j]=R[i];
			j--;
		}
	}
	R[i]=x;
	return i;
}

void QuickSort(int R[],int l,int h)//快速排序
{
	
	int i;
	if(l<h)
	{	
		i=PartitionQuick(R,l,h);	
		QuickSort(R,l,i-1);	
		QuickSort(R,i+1,h);
	}
}


void SelectSort(int R[],int n)//选择排序
{
   int i,j,k;   
	 for(i=n;i>=1;i--)
		 R[i]=R[i-1];	 
   for(i=1;i<n;i++)
   {   	 
     k=i;     
     for(j=i+1;j<=n;j++) 
       if(R[j]<R[k])
         k=j; 
       if(k!=i)
       {        	 
         R[0]=R[i]; 
         R[i]=R[k]; 
         R[k]=R[0]; 
       } 
     }    
     for(i=0;i<n;i++)
		R[i]=R[i+1];
} 


void HeapAdjust(int R[],int i,int n)//堆排序
{ 	 
   int j,temp;
   temp=R[i];
   j=2*i;
   while (j<=n)
   {
	   if (R[j]>R[j+1]&&j<n) 
	  	 j++;
	   if (temp<R[j]) 
	  	 j=n+1;
	   else
	   {
	   	 R[i]=R[j];
     	 i=j;
    	 j=2*i;
     }
   }
   R[i]=temp;
}

int main()
{	
  int R[MAX]={1,82,63,4,65,69,37,98,39,46};
  int i;
  cout<<"|  Please choose the method to sort:  |\n";
  cout<<"|           1 :  InsertSort           |\n";
  cout<<"|           2 :  ShellSort            |\n";
  cout<<"|           3 :  BubbleSort           |\n";
  cout<<"|           4 :  QuickSort            |\n";
  cout<<"|           5 :  SelectSort           |\n";
  cout<<"***************************************\n";
while(true)
{
	cout<<"ENTER i=";
	cin>>i;
	switch(i)
	{
      case 1:
        InsertSort(R,10);	
        cout<<"The result of InsertSort is:"<<endl;break;
      case 2:
        ShellSort(R,10);	
        cout<<"The result of ShellSort is:"<<endl;break;
      case 3:
        BubbleSort(R,10);	
        cout<<"The result of InsertSort is:"<<endl; break;
      case 4:
        QuickSort(R,0,9);		
        cout<<"The result of BubbleSort is:"<<endl;break;
      case 5:
        SelectSort(R,10);	
        cout<<"The result of SelectSort is:"<<endl;break;     
      default:
       return 0;
    }
    //输出插入排序的结果
	  for(i=0;i<10;i++)
		  cout<<setw(3)<<R[i];		
	  cout<<endl;
}
 return 0;
}