这个是热情的写的。我顺便拿他的来用。其他就是我写的了。整理成一个贴子算了 二路归并 #include<iostream> using namespace std;
template <typename T>struct Node{ T key;
}; template <typename T>class Orderedlist{ int maxsize; int last; Node<T> slist[100]; public: Orderedlist(){last=0;maxsize=100;} int Length() const{return last+1;}//计算表长度 void Mergesort(); void MergePass(Node<T> *b,int len); void Merge(Node<T> *b,int low,int mid,int high); bool Insert(Node<T> & elem,int i); void print(); }; template <typename T> bool Orderedlist<T>::Insert(Node<T> & elem ,int i){ if (i<0||i>last+1||last==maxsize-1) return false; else{ for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; last++; return true; } } template <typename T> void Orderedlist<T>::print(){ int i; for(i=0;i<last;i++){ cout<<slist[i].key<<'\t'; if(i%8==7) cout<<endl; } cout<<endl; } template<typename T> void Orderedlist<T>::Mergesort(){ int len=1; Node<T> b[100]; while(len<last){ MergePass(b,len); len=2*len; for(int i=0;i<last;i++) slist[i]=b[i]; } } template <typename T> void Orderedlist<T>::MergePass(Node<T> *b,int len){ int i,j; i=0; while(i+2*len<last){ Merge(b,i,i+len-1,i+2*len-1); i= i+2*len; } if(i+len<last) Merge(b,i,i+len-1,last-1); else for(j=i;j<last;j++) b[j]=slist[j]; } template <typename T> void Orderedlist<T>::Merge(Node<T> *b,int low,int mid,int high){ int i,j,k; i=low; j=mid+1; k=low; while((i<=mid)&&(j<=high)){ if(slist[i].key<=slist[j].key) b[k++]=slist[i++];//取小者复制 else b[k++]=slist[j++]; } while(i<=mid) b[k++]=slist[i++];//复制第一个文件的剩余元素 while(j<=high) b[k++]=slist[j++];//复制第二个文件的剩余元素 }
void main(){ const int h=5; int i; Orderedlist<int> ordlist; int a[h]={5,4,3,2,1}; Node<int> n[h]; for(i=0;i<h;i++) n[i].key=a[i]; for(i=0;i<h;i++) ordlist.Insert(n[i],i); //建立顺序表 cout<<"未排序表："<<endl; ordlist.print(); ordlist.Mergesort(); cout<<"已排序表："<<endl; ordlist.print(); } ----------------------------------------------------------------------------------------------
堆排序 #include<stdio.h> void CreatHeap(int a[],int n,int h) { int i,j,flag,temp; i=h; j=2*i+1; temp=a[i]; flag=0; while(j<n && flag!=1) { if(j<n-1 && a[j]<a[j+1]) j++; if(temp>a[j]) flag=1; else { a[i]=a[j]; i=j; j=2*i+1; } } a[i]=temp; } void InitCreatHeap(int a[],int n) { int i; for(i=(n-1)/2;i>=0;i--) CreatHeap(a,n,i); } void HeapSort(int a[],int n) { int i,temp; InitCreatHeap(a,n); for(i=n-1;i>0;i--) { temp=a[0]; a[0]=a[i]; a[i]=temp; CreatHeap(a,i,0); }
} main() { int n,i,a[100]; printf("请问你要输入几个排序数:\n"); scanf("%d",&n); printf("请输入你要排序的数值:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); HeapSort(a,n); printf("排序后的:\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); } ------------------------------------------------------------- 对半排序 #include<stdio.h> main() { int i,j,temp, low,high,mid,a[100],n; printf("请问你要输入几个数字:\n"); scanf("%d",&n); printf("请输入数字:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++) { temp=a[i]; low=0; high=i-1; while(high>=low) { mid=(low+high)/2; if(temp<a[mid]) high=mid-1; else low=mid+1; } for(j=i-1;j>=low;j--) a[j+1]=a[j]; a[low]=temp; } printf("排序后的:\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); } --------------------------------------------- 快速排序 #include<stdio.h> void QuickSort(int a[],int low,int high){ int i=low,j=high; int temp=a[low]; while(i<j) { while(j>i&&temp<=a[j]) j--; if(j>i) { a[i]=a[j]; i++; } while(j>i&&a[i]<temp) i++; if(j>i) { a[j]=a[i]; j--; } } a[i]=temp; if(low<i) QuickSort(a,low,i-1); if(i<high)QuickSort(a,j+1,high); } main() { int a[100]; int high ,low,i,n; printf("请问你要输入几个数字:\n"); scanf("%d",&n); printf("请输入数字:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); low=0; high=n-1; QuickSort(a,low,high); printf("排序后的:\n"); for( i=0;i<n;i++) printf("%d\t",a[i]); } -------------------------------------- 冒泡 #include<stdio.h> main() {int i,j,temp,n,a[100],flag=1; printf("请问你要输入几个排序数:\n"); scanf("%d",&n); printf("请输入你要排序的数值:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n&&flag==1;i++) { flag=0; for(j=1;j<n-i;j++) if(a[j]<a[j-1]) { flag=1; temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } printf("排序后的:\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); } --------------------------------------------------------- 希尔 #include<stdio.h> void ShellSort(int a[],int n,int d[],int numOfD) { int i,j,k,m,span,temp; for(m=0;m<=numOfD;m++) { span=d[m]; for(k=0;k<span;k++) { for(i=k;i<n-span;i=i+span) { temp=a[i+span]; j=i; while(j>-1&&temp<=a[j]) { a[j+span]=a[j]; j=j-span; } a[j+span]=temp; } } }
} main() {int a[100], b[10],n,i,k,j; printf("请问你要输入几个数字:\n"); scanf("%d",&n); printf("请输入数字:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); j=n; k=0; do{ j=j/2; b[k]=j; k++; }while(j>0); ShellSort(a,n,b,k); printf("排序后的:\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); } --------------------------------------------- 选择排序 #include<stdio.h> main() {int a[100], min,i,k,temp,j,cout; printf("请问你要输入几个数字(不要超过100个！！):\n"); scanf("%d",&cout); printf("请输入数字:\n"); for(i=0;i<cout;i++) scanf("%d",&a[i]); for(i=0;i<cout;i++) { min=i; for(k=i+1;k<cout;k++) { if(a[min]>a[k]) { min=k; } }if(i!=min) { temp=a[i]; a[i]=a[min]; a[min]=temp; } } for(j=0;j<cout;j++) printf("%d\t",a[j]); } ------------------------------------------ 直接插入 #include<stdio.h> main() { int i,j,n,temp,a[100]; printf("请问你要输入几个数字:\n"); scanf("%d",&n); printf("请输入数字:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n-1;i++) { j=i; temp=a[i+1]; while(temp<a[j]&&j>-1) { a[j+1]=a[j]; j--; } a[j+1]=temp; } printf("排序后的:\n"); for(i=0;i<n;i++) printf("%d\t",a[i]); } 有什么问题就说出来。我好更改。
[此贴子已经被作者于2005-8-25 7:41:05编辑过]
