线性时间排序.pptx

算法设计与分析;至今为止，我们见过的排序都是 比较排序 : 仅仅使用比较来比较各项的相对顺序 .;排序〈a1, a2, …, an〉;排序 〈a1, a2, a3〉 = 〈9 , 4 , 6 〉:;每个内部节点标识为i:j,i,j∈{1, 2,…, n}. ?左子树表示当ai≤aj时的比较序列 . ?右子树表示当ai≥aj时的比较序列 .;每个内部节点标识为i:j,i,j∈{1, 2,…, n}. ?左子树表示当ai≤aj时的比较序列 . ?右子树表示当ai≥aj时的比较序列 .;每个内部节点标识为i:j,i,j∈{1, 2,…, n}. ?左子树表示当ai≤aj时的比较序列. ?右子树表示当ai≥aj时的比较序列.; 决策树可以模拟任何的比较排序的执行过程: 每个输入大小为n的序列都可以用这棵树表示. 将算法视为每次两个项相比后就分叉. 树包含了所有可能比较的指令路径. 算法的运行时间 = 路径的长度. 最坏运行时间 = 树的高度.;定理.对n个项排序的任何决策树的高度是Ω(nlgn).; 推论.在最差情况下，任何一种比较排序至少需要O(nlogn)比较操作。这是比较操作所获的信息有限所导致的，或者说是全序集的模糊代数结构所导致的。从这个意义上讲，堆排序和合并排序是渐进最佳的比较排序算法 .;计数排序: 各项之间不进行比较. ?输入: A[1 . . n], A[j]∈{1, 2, …, k}. ?输出: B[1 . . n], 有序. ?辅助存储: C[1 . . k].;for i←1 to k do C[i] ←0 for j←1 to n do C[A[j]] ← C[A[j]] + 1 ? C[i] = |{key = i}| for i←2 to k do C[i] ←C[i] + C[i–1] ? C[i] = |{key ≤i}| for j←n downto1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;5/9/2013;for i←1 to k do C[i] ←0;for j←1 to n do C[A[j]] ←C[A[j]] + 1 ? C[i] = |{key = i}|;for j←1 to n do C[A[j]] ←C[A[j]] + 1 ? C[i] = |{key = i}|;for j←1 to n do C[A[j]] ←C[A[j]] + 1 ? C[i] = |{key = i}|;for j←1 to n do C[A[j]] ←C[A[j]] + 1 ? C[i] = |{key = i}|;for j←1 to n do C[A[j]] ←C[A[j]] + 1 ? C[i] = |{key = i}|;for i←2 to k do C[i] ←C[i] + C[i–1] ? C[i] = |{key ≤i}|;for i←2 to k do C[i] ←C[i] + C[i–1] ? C[i] = |{key ≤i}|;for i←2 to k do C[i] ←C[i] + C[i–1] ? C[i] = |{key ≤i}|;for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1;for;如果 k = O(n), 那么计数排序用的时间为 (n). ?但是, 排序的时间是Ω(nlgn)! ?问题出在什么地方? 答案: ?比较排序 的时间是 Ω(nlgn) . ?计数排序不是 比较排序. ?实际上, 各项之间根本没有比较!;计数排序是一种稳定排序: 它会保持相等的项的相对顺序.;? 发源 : Herman Hollerith 为 1890年美国人口普查设计的卡排序机 (参考附录);5/9/2013;数