算法业计与分祈 合并两个已排列的表 ◆A=[3,5,7,18,1946] ◆B=[1,4,6,16,17,23,31,45,47] ◆C=[1,3,4, 56,7,16,17,18,19,23,31,45,46,47 算法设计与分析
算法设计与分析 11 合并两个已排列的表 w A=[3,5,7,18,19,46] w B=[1,4,6, 16,17, 23,31, 45,47] w C=[ 3, 5,6,7,16,17,18,19,23,31,45,46,47] 1, 4
算法计与分析 ◆ Comment::B[Dp.r] ◆S←p;t←q+1k←p ◆ while s <q and tsr ◆ifA[s]≤At]then ◆B[k]←A[S] s←S+1 else B|k]←A[t ◆t←t+1 ◆ end if e◆k←k+1 ◆ end while ◆ifs=q+ I then B[k.r←A[t.r] ◆eleB[k.r←A[s..q] end if A[pr]←Bp.r算法设计与分析
算法设计与分析 12 w Comment: B [[ p…r ] w s ←p;t ←q+1;k ←p w while s ≤q and t ≤r w if A[s ] ≤A[t ] then w B[k ] ←A[s ] w s ←s+1 w else w B[k ] ←A[t] w t ←t+1 w end if w k ←k+1 w end while w if s=q+1 then B[k…r] ←A[[t…r ] w else B[k…r] ←A[s…q] w end if w A[p…r] ←B[p…r]
算法业计与分析 ◆ template< class t>∥(C语言) void Merge(T cl, t dl, int l, int m, int r) 团/把c[:m和c[m:门归并到d[:n]; inti= m+1 ◆ while(<=m)&&(<=r) if(ct<=cl] d k++=c[i++] ◆ else d[k++]=c[++] e. if(i> m)for(int q=j; q<=r; 9++) ◆d[k++]=c[q]; o else for(int q=i; gs=m; q++) ◆d[k++]=c[q]; 算法设计与分析
算法设计与分析 13 w template<class T> //(C语言） w void Merge(T c[], T d[], int l, int m, int r) w {// 把c [l: m] 和c [m: r] 归并到d [l : r] ;. w int i = l, w j = m+1, w k = l; w while ((i <= m) && (j <= r)) w if (c[i] <= c[j]) d[k++] = c[i++]; w else d[k++] = c[j++]; w if (i > m) for (int q = j; q <= r; q++) w d[k++] = c[q]; w else for (int q = i; q <= m; q++) w d[k++] = c[q]; w }
算法计与分祈 选择排序 K for i←lton k<1 ◆forj←-i+lton ◆ifA[Ak] then k←j end for if k*i then end for 算法设计与分析
算法设计与分析 14 选择排序 w for i←1 to n-1 w k ←i w for j ←i+1 to n w if A[j]<A[k] then k ←j w end for w if k≠i then w end for
算法业计与分祈 ◆ template< class T>∥(C语言) void Selection Sort(T al, int n) {/及时终止的选择排序 ◆ bool sorted= false for (int size =n; isorted &&(size >1); size --)& ◆ int pos=0; ◆ sorted=true; ◆∥找最大元素 for (int i=l; i< size; i++) if(alpos<=ai pos=i else sorted= false;∥/未按序排列 Swap(alpos a size-ID) 算法设计与分析
算法设计与分析 15 w template<class T> //(C语言） w void SelectionSort(T a[], int n) w {// 及时终止的选择排序 w bool sorted = false; w for (int size = n; !sorted && (size > 1); size- -) { w int pos = 0; w sorted = true; w // 找最大元素 w for (int i = 1; i < size; i++) w if (a[pos] <= a[i]) pos = i; w else sorted = false; // 未按序排列 w Swap(a[pos], a[size - 1 ] ) ; w } w }