算法导引.ppt

算法导引 Hu junfeng 2009/12/02 内容 分治思想 贪心 动态规划 基本概念 排序（Sorting）： 简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序） 排序码 与 关键码（primary key） 作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。 排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。 参与排序的对象，称为记录。一个记录可以包含多个字段。 如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。 排序的类型 排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。 在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。 直接插入排序 基本思想： 假定前面m 个元素已经排序； 取第(m+1) 个元素，插入到前面的适当位置； 一直重复，到m=n 为止。 （初始情况下，m = 1） 二分法插入排序算法 void binSort(SortObject * pvector) {int i, j, left, mid, right;RecordNode temp;for( i = 1; i pvector-n; i++ ) { temp = pvector- record[i]; left = 0; right = i – 1;  while (left = right) { mid = (left+right)/2； if (temp.key vector-record[mid].key) right = mid-1; else left = mid+1; }//while for(j=i-1; j=left; j--) pvector-record[j+1] = pvector-record[j]; if(left != i) pvector-record[left] = temp; }// for } // binSort 快速排序 (Quick Sort) 分治法 int DC(x) { if (x) 够简单 return C(x); else 将 x 分解为 x1 - xn for( i=0; in;++i) DC(xi); 重组 DC(xi) 得到 C(x); } 归并排序（merge sort） 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。 最简单的情况是(base case)，只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。 分治法的思路（divide and conquer ） 假设有序列A, 如果能将其平均分为A/2的两个序列A1,A2且分别使得A1,A2排序。 然后就可以通过一个简单的步骤实现A的排序 3，5，7，9 2，6，8，12 归并排序（merge sort） 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。 最简单的情况是:只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。 归并排序（merge sort） Merge Sort Merge Sort Counting sort （8.2） COUNTING-SORT(A, B, k) 1 (for i ← 0 to k) do C[i] ← 0 //initialize C[i] 2 (for j ← 1 to length[A] ) do C[A[j]] ← C[A[j]] + 1 //C[i] now contains the number of elements equal to i. 3 (for i ← 1 to k) do C[i] ← C[i] + C[i - 1]