经典的排序算法C++实现大全

#include<iostream.h> #include<math.h> #include<stdio.h> #define MAXINT 32767 #define MAX 20 int sort(int *data,int n);/*锦标排序*/ int main() { int data[MAX]; int i,n; n=MAX; cout<<"input the numbers that you want to sort(<=20):"<<endl; cin>>n; if(n>20) { cout<<"Sorry! Please input a number again:"<<endl; cin>>n; } cout<<"please input "<<n<<" number to sort:"<<endl; for(i=0;i<n;i++) { cin>>data[i]; } sort(data,n); cout<<"\nSorted:"<<endl; for(i=0;i<n;i++) { cout<<data[i]<<" "; } cout<<endl; return 0; } int sort(int *data,int n) { int *tree; int lChild,rChild,rt; int i,j,k,ii,exp; if(n<2) return 1; /*计算数的层数*/ exp=1; for(i=1;exp<n;i++) { exp=exp+exp; } k=i; /*计算数的结点*/ exp=1; for(i=1;i<k;i++) { exp=exp+exp; } exp=exp-1; exp=exp+n; //tree=malloc(exp*sizeof(int)); tree=new int[exp]; /*将待排序的关键字值移植到叶子节点上*/ j=n-1; for(i=exp-1;i>=exp-n;i--) { tree[i]=data[j]; j--; } /*第一趟搜索最小叶子节点*/ for(;i>-1;i--) { lChild=MAXINT; rChild=MAXINT; ii=(i+1)+(i+1); if(ii<=exp) { lChild=tree[ii-1]; } if(ii+1<=exp) { rChild=tree[ii]; } if(lChild<rChild) { tree[i]=lChild; } else { tree[i]=rChild; } } j=0; data[j]=tree[0]; j++; /*第二趟及其后续各趟排序*/ while(j<n) { /*设置选中的叶子结点值为MAXINT*/ rt=tree[0]; i=0; do { ii=(i+1)+(i+1); if(ii<=exp) { lChild=tree[ii-1]; if(rt==lChild) i=ii-1; } if(ii+1<=exp) { rChild=tree[ii]; if(rt==rChild) i=ii; } ii=(i+1)+(i+1); /*确定叶子结点*/ if(ii>exp) { tree[i]=MAXINT; break; } }while(i+1<=exp); /*查找本轮中最小的结点*/ while(i>0) { i=(i+1)/2; i=i-1; lChild=MAXINT; rChild=MAXINT; ii=(i+1)+(i+1); if(ii<=exp) { lChild=tree[ii-1]; } if(ii+1<=exp) { rChild=tree[ii]; } if(lChild<rChild) { tree[i]=lChild; } else { tree[i]=rChild; } } /*将选中的最小结点移到data数组中*/ data[j]=tree[0]; j++; } //free(tree); delete []tree; return 0; }