算法导论 chapter2

2.1 插入排序法 输入： n个数的一个序列<a1, a2, ... , an>。 输出： 输入序列的一个排列<a1_, a2_, ... , an_>。 希望被排序的数称为关键词(key)。 插入排序法伪代码： INSERTION-SORT(A) 1 for j = 1 to A.length-1 2      key = A[j] 3      // Insert A[j] into the sorted squence A[1,..,j-1]. 4      i = j - 1 5       while i > 0 and A[i] > key 6           A[i+1] = A[i] 7           i = i - 1 8      A[i+1] = key 算法具体分析： 1.下标j表示需要被插入的数据的索引值 2.在 for循环(循环变量为j)每次迭代的开始，包含元素A[1..j-1]的子列表示当前排列好的序列

算法的c++代码实现:

#include<iostream> using namespace std; void insortion_sort(int* A, int n){ for (int j = 1; j != n; ++j){ int key = A[j]; int i = j - 1; while (i >= 0 && A[i] > key){ A[i + 1] = A[i]; i--; } A[i + 1] = key; } } int main() { int A[] = { 2, 4, 6, 7, 3, 1, 9, 10, 56, 34 }; int n = sizeof(A) / sizeof(A[0]); insortion_sort(A, n); for (int j = 0; j != n; ++j) cout << A[j] << " "; cout << endl; return 0; } 2.1习题选做

2.1-3 考虑以下查找问题： 输入： n个数的一个序列A=<a1,...,an>和一个值v 输出： 下标i使得v=A[i]或者当v不在A中出现时，v为特殊值NIL 要求： 线性查找伪代码 我的解答： 线性查找伪代码： LINEAR-SEARCH(A， v) 1 for j = 0 to A.length-1 2       if A[j] == v 3           return i 4 v = NIL 5 return v 2.1-4 考虑两个n位二进制整数相加的问题，写出伪代码。 我的解答： 分析：两个n为二进制相加，按位从右到左逐位相加(进位位用carry表示) 1）求A[j]和B[j]按位相加后对应C[i]，考虑上一位的进位 2）求进位为carry 两个n位二进制相加伪代码： ADD-BINARY(A, B) 1 for j=0 to n 2      C[j] = 0 3 carry = 0 4  for j = 0 to n-1 5      C[j] = (A[j] + B[j] + carry ) % 2 6      carry = (A[i] + B[i] +carry) / 2 7 C[n] = carry 8 return C 算法的c++代码实现: #include<iostream> using namespace std; int* add_binary(int* A, int* B){ const int n = 5; static int C[n+1] = { 0 }; int carry = 0; for (int j = 0; j != n; ++j) { C[j] = (A[j] + B[j] + carry) % 2; carry = (A[j] + B[j] + carry) / 2; } C[n] = carry; for (int j = 0; j != n + 1; ++j){ cout << C[j] << " "; } cout << endl; return C; } int main() { int a[] = { 1, 1, 0, 1, 0 }; int b[] = { 1, 0, 0, 1, 1 }; add_binary(a, b); return 0; } 2.2习题选做 2.2-2 选择排序：找出A中最小的元素与A[1]交换，然后选择次小的元素与A[2]交换，以此类推... 选择排序伪代码： SELECTIVE-SORT(A) 1 for j = 0 to A.length - 2 2      min  = j 3       for i = j +１ to A.length - 1 4           if A[i] < A[min] 5                min = i 6      temp = A[min] 7      A[min] = A[j] 8      A[j] = temp 2.2归并排序法 归并排序法遵循分治模式： 分解：分解待排序的n个元素的序列成各具n/2的两个子序列 解决：使用归并排序递归的排序两个子列 合并：合并两个已排序的子序列以产生已排序的答案 算法具体分析： 1.采用递归调用，当待排列序列的长度为1时，递归“开始回升” 2.归并算法的关键步骤是“合并”，即合并已排好序的两列序列，通过一个辅助的过程MERGE(A, p, q, r)来实现 3.将MERGE作为MERGE-SORT的子函数，MERGE-SORT递归调用自身 合并函数伪代码： MERGE(A, p, q, r) 1      n1 = q - p + 1 2      n2 = r - q 3       for j = 0 to n1 - 1 4           L[j] = A[p+j] 5      for j = 0 to n2 - 1 6      R[j] = A[q+j] 7      L[n1] = ∞ 8      R[n2] = ∞ 9      i = 0 10    j = 0 11       for k = p to r 12            if L[i] <= R[j] 13                A[k] = L[i] 14                i = i + 1 15           else A[k]  =R[j] 16                j = j +1 将MERGE作为MERGE-SORT子程序 归并排序伪代码： MERGE-SORT(A, p, r) 1 q = (p + r) / 2 2 MERGE-SORT(A, p, q) 3 MERGE-SORT(A, q+1, r) 4 MERGE(A, p, q, r) 算法的c++代码实现: #include<iostream> using namespace std; /********************************************/ /* merge函数，用于将序列分解合并实现序列，接口如下： A: 表示待排序的序列，分成两个部分 p: 表示A序列开始的索引值 q：表示两个已排好序序列在A中的分界 r：表示A序列最后的索引值 */ /********************************************/ void merge(int* A, int p, int q, int r){ int n1 = q - p + 1; int n2 = r - q; int *L = new int[n1+1]; int *R = new int[n2+1]; for (int i = 0; i < n1; ++i) L[i] = A[p + i]; for (int i = 0; i < n2; ++i) R[i] = A[q + 1 + i]; L[n1] = INT_MAX; //暂时把INT_MAX(整形最大值)作为哨兵位 R[n2] = INT_MAX; for (int k = p, i = 0, j = 0; k <= r; ++k){ if (L[i] <= R[j]){ A[k] = L[i]; i++; } else{ A[k] = R[j]; j++; } } delete []L; delete []R; } void merge_sort(int* A, int p, int r){ if (p < r){ int q = (p + r) / 2; merge_sort(A, p, q); merge_sort(A, q + 1 , r); merge(A, p, q, r); } } int main() { int A[] = { 9, 15, 13}; merge_sort(A, 0, 2); for (int i = 0; i != 3; ++i) cout << A[i] << " "; cout << endl; return 0; } 2.3习题选做 2.3.2重写过程MERGE，使之不使用哨兵，而是一旦数组L或R的所有元素均被复制回A就立即停止。 不带哨兵的 MERGE伪代码 MERGE(A, p, q, r) 1   n1 = q - p + 1 2   n2 = r - q 3   let L[0 .. n1-1] and R[ .. n2-1] be new arrays 4   for i = 1 to n1 - 1 5       L[i] = A[p + i - 1] 6   for j = 0 to n2 - 1 7       R[j] = A[q + j] 8   i = 0 9   j = 0 10 k = p 11 while n1!=i and n2!=j 12     if R[i] <= L[j] 13        A[k++] = R[i++] 14     else A[k++] = L[j++] 15 while i < n1 16      A[k++] = L[i++] 17 while j < n2 18      A[k++] = L[j++] 算法的c++代码实现: #include<iostream> using namespace std; void merge(int* A, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; int* L = new int[n1]; int* R = new int[n2]; for (int i = 0; i < n1; i++) L[i] = A[p + i]; for (int i = 0; i < n2; i++) R[i] = A[q + 1 + i]; int i = 0, j = 0, k = p; while (i < n1 && j < n2) { if (L[i] <= R[j]) A[k++] = L[i++]; else A[k++] = R[j++]; } while (i < n1) { A[k++] = L[i++]; } while (j < n2) { A[k++] = R[j++]; } delete[] R; delete[] L; } void merge_sort(int* A, int p, int r){ if (p < r){ int q = (p + r) / 2; merge_sort(A, p, q); merge_sort(A, q + 1, r); merge(A, p, q, r); } } int main() { int A[] = { 13, 12, 11, 19, 18, 90, 54, 89, 76 }; merge_sort(A, 0, 8); for (int i = 0; i != 9; i++) cout << A[i] << " "; cout << endl; return 0; }