当前位置: 首页 > >

LAB6 算法排序 快速排序堆排序

发布时间:

四、源程序代码
#define N 10 int compare[6]={0,0,0,0,0,0},change[6]={0,0,0,0,0,0}; void input(int s[]) { int test[N]; srand((unsigned)time(NULL)); for(int i=0;i<N;i++) { test[i]=rand()%100; for(int j=0;j<i;j++) while(test[j]==test[i]) { test[i]=rand()%N; j=0; } } for(i=0;i<=N-1;i++) s[i]=test[i]; } void swap(int &a,int &b) { int tmp; tmp=a; a=b; b=tmp; } void insertsort(int s[]) { int i,j; int a[N+1]; for(i=1;i<=N;i++) { a[i]=s[i-1]; } for(i=2;i<=N;i++) { a[0]=a[i]; for(j=i;j>0&&a[0]<a[j-1]&&(++compare[0]);j--) { a[j]=a[j-1]; change[0]++; }

a[j]=a[0]; change[0]++; } } void bubble_sort(int s[],int n) { int i,j,temp,a[N]; for(i=0;i<n;i++) { a[i]=s[i]; } for(i=0;i<n-1;i++) { for(j=0;j<n-i-1;j++) { compare[1]++; if(a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; change[1]++; } } } } int partition(int a[],int low,int high) { int t,key; t=a[low]; key=a[low]; while(low<high) { while(low<high&&a[high]>=key) { high--; ++compare[2]; } if(low<high) { a[low]=a[high]; low++;

change[2]++; } while(low<high&&a[low]<=key) { low++; ++compare[2]; } if(low<high) { a[high]=a[low]; high--; change[2]++; } a[low]=t; } return low; } void quicksort(int a[],int low,int high) { int key; if(low<high) { key=partition(a,low,high); quicksort(a,low,key-1); quicksort(a,key+1,high); } } void selectsort(int s[],int n) { int i,j,k,a[N]; int t; for(i=0;i<n;i++) { a[i]=s[i]; } for(i=0;i<n-1;i++) { j=i; for(k=i+1;k<=n-1;k++) { if(a[k]<a[j]&&(++compare[3])) j=k; } if(j!=i)

{ t=a[i]; a[i]=a[j]; a[j]=t; change[3]++; } } } void shellinsertsort(int s[],int n) { int i,k,a[N]; k=int(n/2); for(i=0;i<n;i++) { a[i]=s[i]; } for(int gap = n/2; gap > 0; gap /= 2) { for(int i = gap; i < n; i++) { int tmp = a[i]; int j = i; for(; j > 0 && tmp < a[j-gap]; j -= gap) { a[j] = a[j-gap]; compare[4]++; } a[j] = tmp; change[4]++; } } } void heap_adjust(int array[],int i,int len) { int rc = array[i]; for(int j = 2 * i; j <len; j *= 2) { if(j < len && array[j] < array[j+1]) j++; { compare[5]++; if(rc >= array[j]) break; }

array[i] = array[j]; i = j; } array[i] = rc; } void heap_sort(int a[],int len) { int i; for(i = (len-1)/2; i >= 0; i--) heap_adjust(a,i,len); for( i = (len-1); i > 0; i--) { swap(a[0],a[i]); change[5]++;//弹出最大值,重新对 i-1 个元素建堆 heap_adjust(a,0,i-1); } }

void CMyDlg::OnButton1() { // TODO: Add your control notification handler code here UpdateData(TRUE); int s[10],a[10]; input(s); for(int i=0;i<N;i++) { a[i]=s[i]; } CString str[100]; for(i=0;i<100;i++) str[i]=a[i]; for(i=0;i <N;i++) { str[i].Format("%i,",a[i]); //把整型数组添加到字符串 m_shuju1+=str[i]; } insertsort(s); m_zhijie1=compare[0]; m_zhijie2=change[0];

quicksort(a,0,N-1); m_kuaisu1=compare[2]; m_kuaisu2=change[2]; selectsort(s,N); m_jiandan1=compare[3]; m_jiandan2=change[3]; shellinsertsort(s,N); m_xier1=compare[4]; m_xier2=change[4]; heap_sort(a,N); m_dui1=compare[5]; m_dui2=change[5]; bubble_sort(s,N); m_maopao1=compare[1]; m_maopao2=change[1]; CString str2[100]; for(i=0;i<100;i++) str2[i]=s[i]; for(i=0;i <N;i++) { str2[i].Format("%i,",a[i]); m_shuju2+=str2[i]; } UpdateData(FALSE); }

//把整型数组添加到字符串

五、调试过程
对于算法的设计,除了希尔排序和堆排序之外,都比较简单,要注意每种排序的起始位 置和哨兵的位置,便可以正确的排出。而希尔排序,尽管是直接插入排序的变形,但应该从 中间位置开始,从后至前选择,但是在程序上不好编出。而堆排序,更是难以控制,只好借 鉴参考。

六、结果分析

由随机数产生的 10 个数,排序后的结果如上图所示,可以发现,快速排序和简单选择 排序比较次数和交换次数均较少,适合使用。




友情链接: