Case Study:快排序算法的并行化 米 快速排序并行算法53的性能 *在算法每次迭代时，可在⊙()时间内构造一级树， 而树高为⊙(Iogn),所以算法53的时间复杂度为 (logn). *在最坏情况下，构造出的树高为⊙()，所以算法 5.3的时间复杂度为⊙(n)。 18 2011/10/18
18 2011/10/18 Case Study:快排序算法的并行化 快速排序并行算法5.3的性能 在算法每次迭代时，可在Θ(1)时间内构造一级树， 而树高为Θ(logn),所以算法5.3的时间复杂度为 Θ(logn)。 在最坏情况下，构造出的树高为Θ(n)，所以算法 5.3的时间复杂度为Θ(n)
Case Study::枚举排序算法的并行化 枚举排序及其串行算法 *枚举排序(Enumeration Sort)是一种最简单的排序算 法，通常也称为秩排序(Rank Sort)。该算法的具体 思想是（假设按关键字递增排序），对每一个待排序 的元素统计小于它的所有元素的个数，从而得到该元 素最终处于序列中的位置。假定待排序的个数存在 a[]小.a[n]中。首先将a[]与a[2]a[n]比较，记录比其 小的数的个数，令其为k,[1]就被存入有序的数组 b[1].b[n]的b[k+1]位置上；然后将a[2]与a[1], a[3]…a[n]比较，记录比其小的数的个数，依此类推。 这样的比较操作共n(n-1)次，所以串行秩排序的时间复 杂度为0（n2)。 19 2011/10/18
枚举排序及其串行算法 枚举排序（Enumeration Sort）是一种最简单的排序算 法，通常也称为秩排序（Rank Sort）。该算法的具体 思想是（假设按关键字递增排序），对每一个待排序 的元素统计小于它的所有元素的个数，从而得到该元 素最终处于序列中的位置。假定待排序的n个数存在 a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较，记录比其 小的数的个数，令其为k，a[1]就被存入有序的数组 b[1]…b[n]的b[k+1]位置上；然后将a[2]与a[1]， a[3]…a[n]比较，记录比其小的数的个数，依此类推。 这样的比较操作共n(n‐1)次，所以串行秩排序的时间复 杂度为O（݊ଶ）。 19 2011/10/18 Case Study:枚举排序算法的并行化