常用数据结构和算法的实现及测试

/* ******************************************** **作者：宋健 **日期：2008.11.1 ** **文件说明：各种排序算法的实现 **版本号：1.0 ******************************************** */ #include "sorting.h" void initArray(int data[],random r) { for(int i=0;i<COUNT;i++) data[i]=r.randomInt(1,100); } void printArray(int data[]) { int words=0; for(int j=0;j<COUNT;j++,words++) { if( words%MAX_WORDS ==0 ) cout<<endl; cout<<data[j]<<" "; } cout<<endl; } void swap(int &x,int &y) { int temp; temp=y; y=x; x=temp; } int maxInArray(int data[],int low,int high) { int largest=low; for(int i=low+1;i<=high;i++) { if(data[largest]<data[i]) largest=i; } return largest; } void bubbleSort(int data[]) { for(int i=0;i<COUNT-1;i++) { for(int j=0;j<COUNT-i;j++) { if(data[j+1]<data[j]) swap(data[j],data[j+1]); } } } void insertSort(int data[]) { for(int i=1;i<COUNT;i++) { int x=data[i]; int j=i-1; while( j>0 && x<data[j] ) { data[j+1]=data[j]; j=j-1; } data[j+1]=x; } } void selectSort(int data[]) { int largest=0; for(int i=COUNT-1;i>0;i--) { largest=maxInArray(data,0,i); swap(data[largest],data[i]); } } void shell(int data[],int increase) { for(int i=increase;i<COUNT;i=i+increase) { int x=data[i]; int j=i-increase; while(j>0 && x<data[j]) { data[j+increase]=data[j]; j=j-increase; } data[j+increase]=x; } } void shellSort(int data[]) { int increase; for(increase=7;increase>0;increase=increase-2) shell(data,increase); } void merge(int data[],int low,int middle,int high) { int left[COUNT]; int right[COUNT]; int leftLength=middle-low+1; int rightLength=high-middle; int i,j; for(i=0;i<leftLength;i++) left[i]=data[low+i]; for(j=0;j<rightLength;j++) right[j]=data[middle+1+j]; left[leftLength]=INT_MAX; right[rightLength]=INT_MAX; i=j=0; for(int x=low;x<=high;x++) { if(left[i]<right[j]) { data[x]=left[i]; i=i+1; } else { data[x]=right[j]; j=j+1; } } } void mergeSort(int data[],int low,int high) { if(low<high) { int middle=(low+high)/2; mergeSort(data,low,middle); mergeSort(data,middle+1,high); merge(data,low,middle,high); } } int partition(int data[],int low,int high) { int key=data[low]; int lastSmall=low; int firstUnsorted; for(firstUnsorted=low+1;firstUnsorted<=high;firstUnsorted++) { if(data[firstUnsorted]<key) { swap(data[lastSmall+1],data[firstUnsorted]); lastSmall=lastSmall+1; } } swap(data[lastSmall],data[low]); return lastSmall; } void quickSort(int data[],int low,int high) { if(low<high) { int x=partition(data,low,high); quickSort(data,low,x-1); quickSort(data,x+1,high); } } void heap(int data[],int root,int heapSize) { int left=2*root+1; int right=left+1; int largest=root; if(left<heapSize && data[left]>data[root]) largest=left; if(right<heapSize && data[right]>data[largest]) largest=right; if(largest != root) { swap(data[root],data[largest]); heap(data,largest,heapSize); } } void buildHeap(int data[]) { int i; if(COUNT%2==0) i=(COUNT-1)/2; else i=COUNT/2; for(;i>=0;i--) { heap(data,i,COUNT); } } void heapSort(int data[]) { int heapSize=COUNT; buildHeap(data); for(int i=0;i<COUNT-1;i++) { swap(data[0],data[heapSize-1]); heapSize=heapSize-1; heap(data,0,heapSize); } }