总结排序算法

#include<iostream> using namespace std; void print(int a[],int len) { for(int i=0;i<len;i++) cout<<a[i]<<'\t'; } //平均情况下的时间复杂度为O（n*n） void DirectInsertSort(int a[],int length) { for(int j=1;j<length;j++) { int tmp = a[j],k=j-1; for(;k>=0&&tmp<a[k];k--) a[k+1]=a[k]; a[k+1] = tmp; } } //希尔排序 void ShellSort(int a[],int len) { for(int step = len/2;step>0;step/=2) { for(int i = step;i<len;i++) { int tmp = a[i],j = i-step; for(;j>=0&&tmp<a[j];j-=step) a[j+step]=a[j]; a[j+step]=tmp; } } } //直接选择排序算法的时间复杂度是O(N*N) //逐个找出最小的元素进行排序 void SimpleSelectSort(int a[],int len) { for(int i=0;i<len;i++) { int k =i; for(int j=i+1;j<len;j++) if(a[j]<a[k]) k=j; swap(a[k],a[i]); } } void PercolateDown(int a[],int hole,int len) { int child,tmp = a[hole]; for(;hole*2+1<len;hole=child) { child = 2*hole+1; if(child<len-1&&a[child+1]>a[child]) child++; if(a[child]>tmp) a[hole]=a[child]; else break; } a[hole]=tmp; } void HeapSort(int a[],int len) { int i; for(i=len/2-1;i>=0;i--) PercolateDown(a,i,len); for(i=len-1;i>0;i--) { swap(a[0],a[i]); PercolateDown(a,0,i); } } //冒泡排序的算法 void BubbleSort(int a[],int len) { for(int i=1;i<len;i++) { bool flag = false; for(int j=0;j<len-i;j++) { if(a[j+1]<a[j]) { swap(a[j+1],a[j]); flag = true; } } if(!flag) break; } } //快速排序的实现,最坏情况下，标准元素是最小的或者是最大的时，此时的时间复杂度是O（n*n） int Sort(int a[],int low,int high) { int tmp = a[low]; while(low<high) { while(low<high&&a[high]>=tmp) high--; a[low]=a[high]; while(low<high&&a[low]<=tmp) low++; a[high]=a[low]; } a[low]=tmp; return low; } void fastsort(int a[],int low,int high) { if(low<high) { int midd = Sort(a,low,high); fastsort(a,low,midd-1); fastsort(a,midd+1,high); } } void FastSort(int a[],int len) { fastsort(a,0,len-1); } //归并排序的实现 void Merge(int a[],int low,int midd,int high) { int *p = new int[high-low+1]; unsigned int i=low,j=midd,k=0; while(i<midd&&j<=high) { if(a[i]<=a[j]) p[k++]=a[i++]; else p[k++]=a[j++]; } while(i<midd) p[k++]=a[i++]; while(j<=high) p[k++]=a[j++]; for(k=0;k<high-low+1;k++) a[low+k]=p[k]; delete []p; } void mergesort(int a[],int low,int high) { if(low<high) { int midd = (low+high)>>1; mergesort(a,low,midd); mergesort(a,midd+1,high); Merge(a,low,midd+1,high); } } void MergeSort(int a[],int len) { mergesort(a,0,len-1); } int main() { int *p = new int[10]; for(int i=0;i<10;i++) p[i]=rand()00; print(p,10); //DirectInsertSort(p,10); //ShellSort(p,10); //SimpleSelectSort(p,10); //HeapSort(p,10); //BubbleSort(p,10); //FastSort(p,10); MergeSort(p,10); print(p,10); }