基于JAVA的快速排序.pdfVIP

VoL 技术交流 微型电脑应用 2010年第26卷第9期 MicrocomputerAppficafions26,No．9．2010 文章编号：1007-757X(2010)10-0048．02 基于JAVA的快速排序 邢素萍 摘要：阐述了排序对数据处理的重要性。采用流行的跨平台的面向对象程序设计语言java实现了快速排序的算法，并从理 论上进行了算法分析。 关键词：信息；数据结构；数据；排序；Java 中图分类号：TP311 文献标志码：A 0引言 数据项，我们称其为关键字(Key)。当待排序记录的关键 字均不相同时，排序结果是惟一的，否则排序结果不惟一。 信息是计算机学科的基础，信息必须以数据的方式，按 在待排序的文件中，若存在多个关键字相同的记录，经过排 一定的规则存储在计算机的存储器中。对数据的操作方法如 序后这些具有相同关键字的记录之间的相对次序保持不变， 增加、插入、删除、查询等既要考虑数据的存储，又要考虑 该排序方法是稳定的；若具有相同关键字的记录之间的相对 数据操作中数据的处理速度等各方面的因素。因此，怎样更 次序发生变化，则这种排序方法是不稳定的。快速排序被认 科学的设计算法，采用哪种程序设计语言能更好地实现算法 为是目前基于比较记录关键字的内部排序中最好的排序方 是非常重要的。 法。 著名的瑞士科学家N．Wirth曾指出：算法+数据结构=程 序。其中数据结构是指数据逻辑结构和物理结构，算法是对 2快速排序的基本思想 数据运算的描述。由此可见，程序实质是对具体问题选择一 种好的数据结构，再设计一个好的算法，而好的算法通常取 快速排序是C．R．A．Hoare提出的一种划分交换排序。此 决于实际问题的数据结构。Java语言作为面向对象的程序设 排序方法采用了一种分治的策略，通常称其为分治法 计语言，它提供了许多特性来持封装，每个数据项均封装在 某个对象中。每条可执行的语句均由某个对象来完成。每个 问题分解为若干个规模更小结构与原问题相似的子问题，递 对象均是某个类的实例或是一个数组。每个类均在一个单继 归地解这些子问题。然后将这些子问题的解组合为原问题的 承的层次结构中定义。Java的单继承层次结构是一种树犁结 解。这样在用递归描述的分治算法的每一层递归上，都有以 下3个步骤： 构，它的根是object类。Java的面向对象的特点使得它特别 适合于数据结构的设计和实现，为程序员提供了一个很好的 分解：将原问题分解为若干个子问题； 开发平台。因而，采用当今流行的跨平台程序设计语言iava 求解：递归地解各子问题，若子问题的规模足够小，则 实现数据结构的设计，可以很好地解决对数据存储方式、处 直接求解； 理方式的具体化问题。另外，利用iava语言程序设计的灵活 组合：将各子问题的解组合成原问题。 性及交互性，实现数据的动态输入，自动、分步、循环执行 若把当前待排序的无序区设为R[10w……higll】，利用上 存储处理过程，并可在Intemet上发布。 面方法叮将快速排序的基本思想描述为： 排序(Sorting)又称分类，广泛地应用在事务处理及各1．分解。在R[Iow……high]任选一个记录作基准，以 种数据加工的过程中，如果数据能够根据某种规则排序，就 此基准将当前无序区划分为左、右两个较小的子区间 能大大提高数据处理的算法效率。如，在英文字典中按英文 字母顺序单词排列单词，使我们可以很快速地从一本厚厚的 区间中所记录的关键字均小于等于基准记录(设基准记录为 字典中找到所要查找的单词。在计算机处理数据之前也要对 其先进行排序，它是计算机程序设计中的一种重要操作。