//                排序算法的实现#include <iostream>using namespace std; //插入排序void swap(int Array[],int i,int j){ int temp=Array[i]; Array[i]=Array[j]; Array[j]=temp;}void InsertSort(int Array[],int n){ for(int i=1;i<n;i++) {  for(int j=i;j>0;j--)  {   if(Array[j]<Array[j-1])    swap(Array,j,j-1);   else break;  } }}//优化插入排序void ImprovedInertSorter(int Array[],int n){ int  Temp; for(int i=1;i<n;i++) {  Temp=Array[i];  int j=i-1;  while((j>=0)&&(Temp<Array[j]))  {   Array[j+1]=Array[j];   j=j-1;  }  Array[j+1]=Temp; }}//二分法插入排序void BinaryInsertSorter(int Array[],int n){ int temp; int left,right,middle; for(int i=1;i<n;i++) {  temp=Array[i];  left=0;right=i-1;  while(left<=right)  {   middle=(left+right)/2;   if(temp<Array[middle])    right=middle-1;   else    left=middle+1;  }  for(int j=i-1;j>=left;j--)   Array[j+1]=Array[j];  Array[left]=temp; }}//优化冒泡排序void ImprovedBubbleSorter(int Array[],int n){ bool NoSwap; for(int i=1;i<n;i++) {  NoSwap=true;  for(int j=n-1;j>=i;j--)  if(Array[j],Array[j-1])  {   swap(Array,j,j-1);   NoSwap=false;  }  if(NoSwap)   return; }} //直接选择排序void StraighSelectSorter(int Array[],int n){ for(int i=0;i<n-1;i++) {  int Smallest=i;  for(int j=i+1;j<n;j++)  {   if(Array[j]<Array[Smallest])    Smallest=j;  }  swap(Array,i,Smallest); }} //Shell排序void ModifiedInsertSort(int Array[],int n,int delta){ for(int i=delta;i<n;i+=delta)   for(int j=i;j>=delta;j-=delta)   {    if(Array[j]<Array[j-delta])     swap(Array,j,j-delta);    else     break;   }}void ShellSorter(int Array[],int n){ for(int delta=n/2;delta>0;delta/=2)  for(int j=0;j<delta;j++)   ModifiedInsertSort(&Array[j],n-j,delta);} //优化的快速排序int SelectPivot(int left,int right){ return (left+right)/2;}int Partition(int Array[],int left,int right){ int  temp; int i=left; int j=right; temp=Array[j]; while(i!=j) {  while((Array[i]<temp)&&(j>i))   i++;  if(i<j)  {   Array[j]=Array[i];   j--;  }  while((Array[j]>temp)&&(j>i))   j--;  if(i<j)  {   Array[i]=Array[j];   i++;  } } Array[i]=temp; return i;}void ImprovedQuickSorter(int Array[],int left,int right){ if(right<=left)  return ; int pivot=SelectPivot(left,right); swap(Array,pivot,right); pivot=Partition(Array,left,right); ImprovedQuickSorter(Array,left,pivot-1); ImprovedQuickSorter(Array,pivot+1,right);} //两路归并排序 void Merge(int Array[],int TempArray[],int left,int right,int middle){ for(int j=left;j<=right;j++)  TempArray[j]=Array[j]; int index1=left; int index2=middle+1; int i=left; while((index1<=middle)&&(index2<=right)) {  if(TempArray[index1]<TempArray[index2])   Array[i++]=TempArray[index1++];  else   Array[i++]=TempArray[index2++]; } while(index1<=middle)  Array[i++]=TempArray[index1++]; while(index2<=right)  Array[i++]=TempArray[index2++];}void MergeA(int Array[],int TempArray[],int left,int right,int middle){ int index1,index2; int i,j,k; for(i=left;i<=middle;i++)  TempArray[i]=Array[i]; for(j=1;j<=right-middle;j++)         TempArray[right-j+1]=Array[j+middle];     for(index1=left,index2=right,k=left;k<=right;k++)  {   if(TempArray[index1],TempArray[index2])    Array[k]=TempArray[index1++];   else    Array[k]=TempArray[index2--];  }} void TwoWayMergeSorter(int Array[],int TempArray[],int left,int right){ if(left<right) {  int middle=(left+right)/2;  TwoWayMergeSorter(Array,TempArray,left,middle);  TwoWayMergeSorter(Array,TempArray,middle+1,right);  MergeA(Array,TempArray,left,right,middle); }} //桶式排序 void BuckerSorter(int Array[],int n,int max){ int *TempArray=new int[n]; int * count=new int[max]; int i; for(i=0;i<n;i++)  TempArray[i]=Array[i]; for(i=0;i<max;i++)  count[i]=0; for(i=0;i<n;i++)  count[Array[i]]++; for(i=1;i<max;i++)  count[i]=count[i-1]+count[i]; for(i=n-1;i>=0;i--)  Array[--count[TempArray[i]]]=TempArray[i];}//基数排序void RadixSorter(int Array[],int n,int d,int r){ int *TempArray=new int[n]; int *count=new int[r]; int i,j,k; int Radix=1; for(i=1;i<=d;i++) {  for(j=0;j<r;j++)   count[j]=0;  for(j=0;j<n;j++)  {   k=(Array[j]/Radix)%r;   count[k]++;  }  for(j=1;j<r;j++)   count[j]=count[j-1]+count[j];  for(j=n-1;j>=0;j--)  {   k=(Array[j]/Radix)%r;   count[k]--;   TempArray[count[k]]=Array[j];  }  for(j=0;j<n;j++)   Array[j]=TempArray[j];  Radix*=r; }}//打印数据void printArray(int Array[],int n){ for(int i=0;i<n;i++)  cout<<Array[i]<<" "; cout<<endl;} int main(){ int array[20],n=10; int sign=0,tempArray[20],max=100; int d=2,r=10; cout<<"Enter some numbar to sort:"<<endl; for(int i=0;i<n;i++) {  cin>>array[i];  tempArray[i]=0; } cout<<"输入你要选择的排序方法:"<<endl; cout<<"插入排序---1"<<"优化插入排序--2"<<"二分法插入排序---3"<<endl; cout<<"优化冒泡--4"<<"直接选择--5"<<"SHELL排序--6"<<endl; cout<<"优化的快速排序--7"<<"两路归并排序---8"<<"桶式排序----9"<<endl; cout<<"基数排序=====10"<<endl; cin>>sign; switch(sign) { case 1: InsertSort(array,n);break; case 2: ImprovedInertSorter(array,n);break; case 3: BinaryInsertSorter(array,n);break; case 4: ImprovedBubbleSorter(array,n);break; case 5: StraighSelectSorter(array,n);break; case 6: ShellSorter(array,n);break; case 7: ImprovedQuickSorter(array,0,n-1);break; case 8: TwoWayMergeSorter(array,tempArray,0,n-1);break; case 9: BuckerSorter(array,n,max);break; case 10: RadixSorter(array,n,d,r);break; default:break; } cout<<"排序的结果是:"<<endl; printArray(array,n); return 0;}

评论