【排序】C/C++常见的几种排序

几种排序"/>

【排序】C/C++常见的几种排序

#include<stdio.h>
#include<iostream>
#include <cstdlib>
#include <time.h>
#define max 50 
using namespace std;//冒泡排序 
void BubbleSort(int A[],int n){int i,j;int temp;for(i=0;i<n-1;i++){for(j=0;j<n-i-1;j++){if(A[j]>A[j+1]){temp=A[j];A[j]=A[j+1];A[j+1]=temp;}}}
}//直接插入排序
void InserSort(int A[],int n){int i,j;for(i=2;i<=n;i++)     //将A2~An插入前面已经排序序列 if(A[i]<A[i-1]){  //若Ai关键码小于其前驱，将Ai插入有序表 A[0]=A[i];    //复制为哨兵A0不存放元素 for(j=i-1;A[0]<A[j];j--)//从后往前查找待插入位置 A[j+1]=A[j];   //向后挪位 A[j+1]=A[0];      //复制到插入位置}	
}    //折半插入排序
void Insert_Half_Sort(int A[],int n){int low,high,mid;int i,j;for(i=2;i<=n;i++){  //将A2~An插入前面已经排序序列 A[0]=A[i];      //将Ai暂存到A0 low=1;          //设置默认查找范围 high=i-1;while(low<=high){       //折半查找（默认增序） mid=(low+high)/2;   //取中间点 if(A[mid]>A[0])    //查找左子表 high=mid-1;else              //查找右子表 low=mid+1;}for(j=i-1;j>=high;j--)A[j+1]=A[j];      //统一后移元素 A[high+1]=A[0];		//插入操作		}
} //希尔排序
void ShellSort(int A[],int n){//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到 int dk;//步长 int i,j;for(dk=n/2;dk>=1;dk=dk/2)   //步长变化 for(i=dk+1;i<=n;i++)if(A[i]<A[i-dk]){     //需将Ai插入有序增量子表 A[0]=A[i];          //暂存在A0 for(j=i-dk;j>0&&A[0]<A[j];j-=dk)A[j+dk]=A[j];   //记录后移，查找插入位置 A[j+dk]=A[0];       //插入 }
}//快速排序 
int Partition(int A[],int low,int high){  //划分算法，一趟划分 int pivot=A[low];        //当前表中第一个元素设为枢轴，对表进行划分 while(low<high){         //循环跳出条件 while(low<high&&A[high]>=pivot) --high;A[low]=A[high];  //比枢纽小的移动到左端 while(low<high&&A[low]<=pivot)++low;A[high]=A[low];//比枢纽大的移动到右端 }A[low]=pivot;//枢轴元素存放到最终位置 return low;  //返回存放枢轴的最终位置 
}
void QuickSort(int A[],int low,int high){	if(low<high){  //跳出递归条件 //Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表 int pivotpos=Partition(A,low,high);//划分 	QuickSort(A,low,pivotpos-1);       //对两个子表进行递归排序 		QuickSort(A,pivotpos+1,high);}
}//选择排序
void SelectSort(int A[],int n){int i,j,min,temp;for(i=0;i<n-1;i++){ //一共进行n-1趟 min=i;          //记录最小元素位置 for(j=i+1;j<n;j++){  //在A[i...n-1]中选择最小的元素 if(A[j]<A[min])  //更新最小元素位置 min=j;        }if(min!=i){temp=A[min];A[min]=A[i];A[i]=temp;}} 
} //堆排序
void HeadAdjust(int A[],int k,int n){//函数HeadAdjust将元素k为根的子树进行调整 int i;A[0]=A[k];  //A[0]暂存子树的根结点 for(i=2*k;i<=n;i*=2){//沿key（关键字）较大的子节点向下筛选 if(i<n&&A[i]<A[i+1])  i++;//取key较大的子结点的下标 if(A[0]>=A[i])break;  //筛选结束 else{A[k]=A[i]; //将Ai调整到双亲结点上 k=i; //修改k值，继续向下筛选 } } A[k]=A[0];//被筛选结点的值放入最终位置 
}
//建立大根堆 
void BuildMaxHeap(int A[],int n){int i;for(i=n/2;i>0;i--){ //从i=[n/2]~1反复调整堆 HeadAdjust(A,i,n); }
} void HeapSort(int A[],int n){int i;int temp;BuildMaxHeap(A,n);//初始建堆 for(i=n;i>1;i--){//n-1趟交换和建堆过程 temp=A[i];A[i]=A[1];A[1]=temp;HeadAdjust(A,1,i-1);//调整，把剩余i-1个元素整理成堆 }
}//归并排序 
//int Help[max];//辅助数组
int *Help=(int *)malloc((max+1)*sizeof(int)); //辅助数组
void Merge(int A[],int low,int mid,int high){//表A的两段A[low..mid],A[mid+1...high]各自有序，将他们合并成一个有序表 int k;int i,j;for(k=low;k<=high;k++)Help[k]=A[k];    //A中所有元素复制到help中 for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){if(Help[i]<=Help[j])  //比较数组Help的左右两段元素 A[k]=Help[i++];    //将较小值复制到A中 elseA[k]=Help[j++];}//ifwhile(i<=mid)        //若第一个表未检测完 ，复制  A[k++]=Help[i++];while(j<=high)        //若第二个表未检测完 ，复制  A[k++]=Help[j++];} void MergeSort(int A[],int low,int high){int mid;if(low<high){mid=(low+high)/2;   //从中间划分两个子序列 MergeSort(A,low,mid);		//对左侧子序列进行递归排序 MergeSort(A,mid+1,high);    //对右侧子序列进行递归排序 Merge(A,low,mid,high);//归并 }
}/*
//折半查找
int Search_Half_find(int A[],int n,int key){int low=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(A[mid]==key)return mid;else if(A[mid]>key)high=mid-1;elselow=mid+1;}return -1;
} *///顺序查找
int Search_Seq(int A[],int n,int key){int i,j;i=0;while(i<n){		   	   if(A[i]==key)return i;	   i++;}return  -1;
} int main()
{int A[max],B[max],C[max],D[max],E[max],F[max],G[max],H[max];int n;int i,j;int x; cout<<"输入一个不大于50的数"<<endl;cin>>n; //随机数srand(time(NULL));cout<<"-----数组A--随机赋值后"<<endl; for(i=0;i<n;i++){A[i]=rand()%100;cout<<A[i]<<" ";} cout<<"\n-----数组A--使用冒泡排序后"<<endl;//冒泡排序 	  BubbleSort(A,n);	 	 for(i=0;i<n;i++)cout<<A[i]<<" ";	   cout<<endl;cout<<endl;//折半查找/*srand(time(NULL));x=rand()%50; cout<<"-----随机生成查找的值X= "<<x<<"\n-----在A中使用折半查找的结果"<<endl; j=Search_Half_find(A,n,x);	if(j!=-1)cout<<j<<endl;elsecout<<"erro"<<endl;cout<<endl;*/cout<<"-----数组B--随机赋值后"<<endl; for(i=1;i<=n;i++){B[i]=rand()%100;cout<<B[i]<<" ";} cout<<endl;//插入排序cout<<"-----插入排序后----"<<endl; InserSort(B,n);for(i=1;i<=n;i++)cout<<B[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组C--随机赋值后"<<endl; for(i=1;i<=n;i++){C[i]=rand()%100;cout<<C[i]<<" ";} cout<<endl;//折半插入排序cout<<"-----选择插入排序后----"<<endl; Insert_Half_Sort(C,n);for(i=1;i<=n;i++)cout<<C[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组D--随机赋值后"<<endl; for(i=1;i<=n;i++){D[i]=rand()%100;cout<<D[i]<<" ";} cout<<endl;//希尔排序cout<<"-----希尔排序后----"<<endl; ShellSort(D,n);for(i=1;i<=n;i++)cout<<D[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组E--随机赋值后"<<endl; for(i=1;i<=n;i++){E[i]=rand()%100;cout<<E[i]<<" ";} cout<<endl;//快速排序 cout<<"-----快速排序 后----"<<endl; QuickSort(E,1,n);for(i=1;i<=n;i++)cout<<E[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组F--随机赋值后"<<endl; for(i=0;i<n;i++){F[i]=rand()%100;cout<<F[i]<<" ";} cout<<endl;//简单选择排序 cout<<"-----简单选择排序后----"<<endl; SelectSort(F,n);	  for(i=0;i<n;i++)cout<<F[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组G--随机赋值后"<<endl; for(i=1;i<=n;i++){G[i]=rand()%100;cout<<G[i]<<" ";} cout<<endl;//堆排序 cout<<"-----堆排序后----"<<endl; HeapSort(G,n);	  for(i=1;i<=n;i++)cout<<G[i]<<" ";	   cout<<endl;cout<<endl;cout<<"-----数组H--随机赋值后"<<endl; for(i=1;i<=n;i++){H[i]=rand()%100;cout<<H[i]<<" ";} cout<<endl;//归并排序 cout<<"-----归并排序 ----"<<endl; MergeSort(H,1,n);	  for(i=1;i<=n;i++)cout<<H[i]<<" ";	   cout<<endl;cout<<endl;return 0;} 

运行结果：