算法业计与分祈 插入排序 ◆例如,如果向数组a[0:5]=[1,2,6, 8,9,11]中插入4,所得到的结果为 a[0:6]=[1,2,4,6,8,9,11] 当我们为新元素找到欲插入的位置时, 必须把该位置右边的所有元素分别向右 移动一个位置。对于本例,需要移动11, 9,8和6,并把4插入到新空出来的位置 a[2]中。 算法设计与分析 16
算法设计与分析 16 插入排序 w 例如，如果向数组a[0:5] = [1, 2, 6, 8, 9,11 ]中插入4，所得到的结果为 a[0:6] = [1, 2, 4, 6, 8, 9, 11 ]。 当我们为新元素找到欲插入的位置时， 必须把该位置右边的所有元素分别向右 移动一个位置。对于本例，需要移动11, 9, 8和6，并把4插入到新空出来的位置 a [ 2 ]中
算法业计与分祈 插入排序 ◆fori←2tom X←A[i J←1-1 XM while (j>0)and(A []>x) A+1]←A[ end while ◆A[+1]←x ◆ end for 算法设计与分析
算法设计与分析 17 插入排序 w for i ←2 to n w x ←A [i] w j ←i-1 w while (j>0) and (A [j]>x) w A[j+1] ←A [j] w j ←j-1 w end while w A[j+1] ←x w end for
计与分 template<class T> void Insert (t a, int n, const T& x) /向有序数组a[0:n-1]中插入元素x ◆inti; ◆for(i=n-1;i六0&x<a[i];i--) a[i+1]=a[i] a[i+1]=x; ◆ template< class t void Insertion Sort (T a[, int n /对a[0:n-1]进行排序 for (int i=1: i<n: i++) Tt=alil Insert(a, i, t) 算法设计与分析
算法设计与分析 18 template<class T> w void Insert(T a[], int n, const T& x) w {// 向有序数组a [0 : n - 1]中插入元素x w int i; w for (i = n-1; i >= 0 && x < a[i]; i- -) w a[i+1] = a[i]; w a[i+1] = x; w } w template<class T> w void InsertionSort(T a[], int n) w {// 对a [ 0 : n-1 ]进行排序 w for (int i = 1; i < n; i++) { w T t = a[i]; w Insert(a, i, t); w } w }
算法鲨计与分祈 插入排序 f template<class t> void InsertionSort(t all, int n) for(int i=l; i< n; i++)i ◆//将a[i插入a[0:i-1l ◆Tt=al[i; ◆intJ 3A+tri=1计>0&&tai}) ◆a[j+1l=ajil; ◆al[j+1=t; 19 算法设计与分析
算法设计与分析 19 插入排序 w template<class T> w void InsertionSort(T a[], int n) w for (int i = 1; i < n; i++) { w / /将a [ i ]插入a [ 0 : i-1 ] w T t = a[i]; w int j; w for (j = i-1; j >= 0 && t < a[j]; j- -) w a[j+1] = a[j]; w a[j+1] = t; w } w }
算法业计与分祈 自底向上合并排序 2)3)4(5(6)7)8(9)10 3(4)5)6(8(9厘0l 5(6)910 3(4)8(11 1)2)7 6 5(9 3)11 4)8 2
算法设计与分析 20 自底向上合并排序 6 10 9 5 5 3 11 4 8 1 2 6 10 5 6 9 10 3 9 3 11 4 8 1 2 4 8 7 7 11 1 2 7 3 4 5 6 8 9 10 11 1 2 7 1 2 3 4 5 6 7 8 9 10 11