面试必考题目+各种排序实例及点评(2)

cout<<\ print_array(a,9); select_sort(a,9); cout<<\ print_array(a,9); }

f.归并排序：

#include

void Merge(int a[],int tmp[],int lPos,int rPos,int rEnd) { int i,lEnd,NumElements,tmpPos; lEnd=rPos-1; tmpPos=lPos; NumElements=rEnd-lPos+1; while (lPos<=lEnd&&rPos<=rEnd) { if (a[lPos]<=a[rPos]) tmp[tmpPos++]=a[lPos++]; else tmp[tmpPos++]=a[rPos++]; } while(lPos<=lEnd) tmp[tmpPos++]=a[lPos++]; while(rPos<=rEnd) tmp[tmpPos++]=a[rPos++]; for(i=0;i

void msort(int a[],int tmp[],int low,int high) { if (low>=high) return; int middle=(low+high)/2; msort(a,tmp,low,middle); msort(a,tmp,middle+1,high); Merge(a,tmp,low,(middle+1),high); }

void merge_sort(int a[],int len) { int *tmp=NULL; tmp=new int[len]; if (tmp!=NULL) {

msort(a,tmp,0,len-1); delete[]tmp; } }

void print_array(int a[],int len) { for (int i=0;iint main() { int a[5]={8,6,1,3,5}; merge_sort(a,5); print_array(a,5); return 0; }