数据结构-分治算法.ppt

各种排序方法实验比较 实验数据图表表示 14.2.4 选择问题 问题描述 求数组a[0:n-1]中第k小的元素——升序排列中，位于第k个位置的元素 [(12,a),(4,b),(5,c),(4,d),(5,e),(10,f),(2,g),(20,h)]?[(2,g),(4,d),(4,b),(5,c),(5,e),(10,f),(12,a),(20,h) ]k=1：(2, g)k=2：(4, d)k=3：(4, b) 选择问题 特别有用的：中值问题，k=n/2 简单解法：排序，然后取第k元，O(nlogn) 更好的算法：利用快速排序列表划分的方法 一次划分后，pivot位于j j=k，找到 kj，继续对left进行划分 kj，继续对right进行划分 重复上述步骤，直到中央元位置等于k为止 实现 templateclass T T select(T a[], int l, int r, int k) {// Return kth smallest in a[l:r]. if (l = r) return a[l]; int i = l, // left to right cursor j = r + 1; // right to left cursor T pivot = a[l]; 实现（续） // swap elements = pivot on left side // with elements = pivot on right side while (true) { do {// find = element on left side i = i + 1; } while (a[i] pivot); 实现（续） do {// find = element on right side j = j - 1; } while (a[j] pivot); if (i = j) break; // swap pair not found Swap(a[i], a[j]); } 实现（续） if (j - l + 1 == k) return pivot; // place pivot a[l] = a[j]; a[j] = pivot; // recursive call on one segment if (j - l + 1 k) return select(a, j+1, r, k-j+l-1); else return select(a, l, j-1, k); } 复杂性分析 最坏情况显然为Q(n2) 改进 达到Q(n)，中心元选择——“中间的中间” 将n个元素分为n/r组，r为整常数，每组r个元素 对每组r个元素进行排序，O(1) （r为常量，与n无关） ，选出每组中心元素 选取n/r个（非常量）中心元素的中心元素——递归使用选择算法 改进算法例 r=5，n=27，a=[2, 6, 8, 1, 4, 10, 20, 6, 22, 11, 9, 8, 4, 3, 7, 8, 16, 11, 10, 8, 2, 14, 15, 1, 12, 5, 4] 分为6组：[2,6,8,1,4]，[10,20,6,22,11]，[9,8,4,3,7]，[8,16,11,10,8]，[2,14,15,1,12]和[5,4] 每组的中间元素分别为4,11,7,10,12和4 改进算法例 [4,11,7,10,12,4]的中间元素为7——作为pivot left=[2,6,1,4,6,4,3,2,1,5,4]middle=[7]，right=[8,10,20,22,11,9,8,8,16,11,10,8,14,15,12] 若k12，则仅仅需要在left中寻找；k=12，pivot——7即为所求；k12，继续有哪些信誉好的足球投注网站right 分治排序伪代码 templateclass T void sort(T E, int n) { //对E中的n个元素进行排序，k为全局变量 if (n=k) { i=n/k; j=n-i; 令A包含E中的前i个元素 令B包含E中余下的j个元素 sort(A, i); sort(B, j); merge(A,B,E,i,j,);//把A和B合并到E } else 使用插入排序算法对E进行排序 } 复杂性分析 伪代码细化 k=2：二路归并排序（two-way merge sort） 链表描述性能最好 temp