并行计算中快速排序算法改进.docxVIP

PAGE  PAGE 6 并行计算中快速排序算法的改进 摘要：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。排序是计算机科学中最重要的研究问题之一。本文先从串行的快速排序讲起，进而过渡到并行的快速排序算法。串行算法的平均时间复杂为O(nlogn)，而并行算法的平均时间复杂度为O(2logn)，。但是当数据量非常大的时候，传统的快速排序办法理论可行，但实际上却是不可行的。为此，本文提出一种结合归并排序的方法给出一种改进的并行快速排序，得到一个可以用在待排序的数据个数巨大时的实用的并行算法。 关键词：快速排序；归并排序；串行算法；并行算法；时间复杂度 引言 排序是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性，2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一[1]。因此对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛应用[2]。基本的排序问题是重排一个给定的数据项集，使它按递增（或递减）排列。数据项可以是具有线性顺序的任意对象。例如，在典型商业数据处理应用中数据项是记录，每一个记录都包含有一个称为关键字的特殊标识符域，并且记录是按关键字进行排序。排序能够大大简化查找或更新一个记录的过程。到目前为止，尽管研究人员已经设计了多种排序算法。但快速排序仍然是实际应用中最常用的一种排序算法。对它复杂度的分析方法和数据结构的研究是研究许多应用问题的基础。快速排序中使用的分治策略是设计有效计算几何和组合问题算法的典型设计方法。本文将探讨并行计算中快速排序的改进。 快速排序简介 快速排序( Quicksort)［3］是对冒泡排序的一种改进。由C． A． R． Hoare 在1962 年提出。它的基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 快速排序算法是利用分治技术的典型例子。分治策略分为三步。首先将问题分成若干大小基本相等的子问题；独立地解决这些子问题；最后将子问题归并成原问题的解。因此方法的有效性取决于对初始问题划分的过程和最后一步归并解的过程。 假设待排序的n个元素存储在数组A[0, n-1]中。快速排序算法的高级描述如下： (1) 从数组A[0, n-1]中选取枢轴元素。 (2) 重排数组A中元素，并将其划分成左右两部分。使得数组中所有比枢轴元素小的元素在左部分中，比它大的元素在右部分中。 (3) 对左、右部分进行递归排序。 如果先不看实现的细节和算法的正确性证明，不难看出算法使用了分治策略。在这种情况下，第一、二步相应于划分步，第三步求解归约的子问题，实现对整个数组的排序，从而无需归并步骤。在快速排序算法的描述中，忽视了两个关键的问题： (1) 选择枢轴元素的方法； (2) 如枢轴元素被选择后，使用的划分方法。 由于本文主要探讨快速算法的并行化，故采用简化的方法，直接选取数组的首个元素为枢轴元素。 归并排序简介 归并排序[4]（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序具体工作原理如下( 假设序列共有 n 个元素) : ( 1) 将 序 列 每 相 邻 两 个 数 字 进 行 归 并 操 作( merge) ，形成 floor( n /2) 个序列，排序后每个序列包含两个元素; ( 2) 将上述序列再次归并，形成 floor( n /4) 个序列，每个序列包含四个元素; ( 3) 重复步骤( 2) ，直到所有元素排序完毕。 并行算法中的快速排序 并行计算是实现高性能计算的主要技术手段[5]，排序问题是计算机科学中最重要的研究问题之一。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。尽管在最坏情况下，它的平均情况下的时间复杂度相当好[6]。将串行的快速排序并行化，必然能够提高对数据处理的效率。 PRAM－CRCW 上快速排序算法 执行快排序可以看成是构造一棵二叉树，其中主元是根，小于等于主元的元素处于左子树，大于主元的元素处于右子树。算法首先从选第一个主元开始，它划分原序列为两个自序列；然后相继子序列中主元的选取则可并行执行。当这样的二叉树造好后，采用中序遍历的方法就可得到一个有序序列[7]。 令待排序的序列为( A1, …