基于姓名排序算法动态演示系统的设计与实现说明书

更新时间：2023-11-03 23:15:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

各种排序算法动态演示推荐度：
相关推荐

陕西理工学院毕业设计

基于姓名排序算法动态演示系统的设计与实现

[摘要]在有限的资源空间里,为了提高运算处理数据的速率，使用高效算法必不可少。本文以Java作为开发

工具，设计与开发了基于姓名排序算法动态演示系统。该系统实现了插入排序（链表插入排序、直接插入排序、折半插入排序等）、交换排序、选择排序、归并排序、堆排序等算法的动态演示。系统界面美观，操作简单，可作为排序可视化教学演示软件。

[关键词]Java；排序算法；动态演示

The Design and Implementation of Dynamic Presentation

Systems based on Name Sorting Algorithm

Abstract：In the space limited resources, in order to improve the rate of operation of the data processing, the use of

efficient algorithm is essential. In this paper, Java as a development tool, designed and developed based on the name of sorting algorithm dynamic presentation systems. The system implements insertion sort (list insertion sort, insertion sort, binary insertion sort, etc.), exchange sort, selection sort, merge sort, heap sort, such as dynamic presentations algorithm. System interface is beautiful, simple operation, can be used as sort of teaching visual presentation software.

Key words: Java ; Sorting Algorithm;Dynamic Presentation

陕西理工学院毕业设计

引言 ...................................................... 1 1系统背景及意义 ........................................... 2

1.1系统背景 ................................................ 2 1.2系统目的及意义 .......................................... 2 1.3开发工具介绍 ............................................ 2

2排序算法 ................................................. 5

2.1直接插入排序 ............................................ 5 2.2折半插入排序 ............................................ 6 2.3快速排序 ................................................ 6 2.4选择排序 ................................................ 8 2.5归并排序 ................................................ 9 2.6链表插入排序 ........................................... 10 2.7堆排序 ................................................. 11 2.8基数排序（MSD） ........................................ 12

3系统设计 ................................................ 14

3.1系统模块结构 ........................................... 14 3.2 模块算法流程图 ......................................... 14

4实现 .................................................... 21

4.1 直接插入排序 ........................................... 21 4.2 折半插入排序 ........................................... 21 4.3选择排序 ............................................... 22 4.4快速排序 ............................................... 22 4.5归并排序 ............................................... 23 4.6链表插入排序 ........................................... 23 4.7堆排序 ................................................. 24 4.8基数排序（MSD） ........................................ 25

5测试 .................................................... 26 总结 ..................................................... 34 致谢 ..................................................... 35 参考文献 ................................................. 36 科技外文文献 ............................................. 37 附录A:基于姓名排序算法动态演示系统的设计与实现源代码 ..... 47 附录B:使用说明书 ......................................... 80

陕西理工学院毕业设计

引言

计算机技术的日益发展，其应用早已不局限于简单的数值运算。涉及到问题的分析、数据结构框架、以及插入、删除、排序查询等复杂的非数值处理和操作。“数据结构”是计算机程序设计的重要基础，也是计算机相关专业的一门重要基础课程和核心课程。其加强对新数据类型的研究和寻找更适用更完善的数据结构类型，也是今后数据结构研究的重要内容.抽象数据结构类型的出现，使

[1]

得在面向对象的语言中,值和变量的类型不再单一，语言中的操作可以作用于多种类型的对象。因此,要建立良好的数据结构，首先对系统按某种原则进行分解，使系统中各模块间独立性强，依赖性小，结构灵活,易于维护。然而，一个良好的分解，要依赖于抽象，只有对系统抽象到一定的程度，才能更好地分解。由于不以记录为基础的递归数据类型的出现，给许多高级应用领域提供了更好地表达复杂数据对象的方法。数据结构从一维二维向三维和多维数据结构的研究意义以及如何实现它

[2]

们等等，都是数据结构今后研究的重要内容。

[1]

数据结构基本元素内容的发展变化，为数据结构的研究开拓了一个新的方向。许多国内外学者都把数据结构的基本元素——数据，进一步扩充为知识,提出了知识的数据结构概念,这样就在更高层次上表示信息的知识代替了明显表示信息逻辑数据，把表示方法更加复杂的知识代替了较为简单的数据,开拓了数据结构研究的新方向.在原有的数据扩展到知识以后，除了基本元素结构表示的不同需要研究以外，更多地应加强对于基本元素间关系和运算以及它们的多种限定性和变化性方面的研究。总之，数据结构由于其基本元素的内容和本质的不断变化，它作为一门学科也要不断变化和适应新的要求。

各个应用领域迫切需要解决的问题，也是当前数据结构基本的研究内容之一在计算机科学与信息融为一体的今天，研究数据结构，既要从计算机技术的发展考虑，也要从信息技术的发展考虑，特别需要重视从理论到实际的转化研究。许多诸如数据工程多媒介数据库和知识工程等等新发展起

[11]

来的学科，也都大量涉及封数据结构的理论和技术, 迫切要求开拓与之对适应的数据结构。对于初学者，它对程序设计思想的建立、提升有着重要的作用，既为后续的计算机课程奠定了一个较为扎实的基础，又可提高分析问题和解决问题的能力，而排序更是“数据结构”里面的核心内容。排序算法的学习就是为以后利用计算机资源高效开发非数值处理的计算机程序打下坚定的理论、方法和技术基础。因此，本文以java为开发语言，设计开发了基于姓名排序算法动态演示系统，有助于初学者的形象直观的学习排序算法。

第 1 页共 80 页

陕西理工学院毕业设计

1系统背景及意义

1.1系统背景

由于排序在计算机图形、计算机辅助设计、机器人、模式识别、基因排序工程及统计学等领域具有广泛应用，所以对排序的研究既有理论上的重要意义，又有实际应用价值。再加上现在信息产业的迅速发展，信息的流通量越来越大，如此庞大并且杂乱无章的信息数据十分难以管理和查询，就更加需要一种十分快捷而有效的编排手段来整理这些数据信息，让我们的工作效率得以提高[4]。 1.2系统目的及意义

随着计算机技术的发展，各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的地位，且排序在人们的日常生活和学习、科研、生产等各个方面有着重要的应用，因此掌握常用的排序算法是很有必要。在以后的发展中，排序对我们的学习和生活的影响会逐渐增大，因此设计开发一个排序算法动画演示系统，以提高自己对排序算法的掌握程度,并希望该系统有助于初学者直观学习排序算法。此次毕业设计一方面使自己更好的掌握排序的知识，另一方面锻炼一下独立开发系统的能力。

1.3开发工具介绍

(1) Java语言

[8]

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE, JavaME, JavaSE）的总称。Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。Java分为三个体系JavaSE（J2SE）（Java2 Platform Standard Edition，java平台标准版），JavaEE(J2EE)(Java 2 Platform,Enterprise Edition，java平台企业版)，JavaME(J2ME)(Java 2 Platform Micro Edition，java平台微型版)。主要特性：

[10]

Java语言是易学的。Java语言的语法与C语言和C++语言很接近，使得大多数程序员很容易学习和使用Java。另一方面，Java丢弃了C++中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java语言不使用指针，而是引用。并提供了自动的废料收集，使得程序员不必为内存管理而担忧。

[8]

Java语言是强制面向对象的。Java语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为

[10]

implements）。Java语言全面支持动态绑定，而C++语言只对虚函数使用动态绑定。总之，Java语言是一个纯的面向对象程序设计语言。

[10]

Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程接口中有一个网络应用编程接口（java net），它提供了用于网络应用编程的类库，包括URL、URLConnection、Socket、ServerSocket等。Java的RMI（远程方法激活）机制也是开发分布式应用的重要手段。

[10]

Java语言是健壮的。Java的强类型机制、异常处理、垃圾的自动收集等是Java程序健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更具健壮性。 Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制以防恶意代码的攻击。除了Java语言具有的许多安全特性以外，Java对通过网络下载的类具有一个安全防范机制（类ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类SecurityManager）让Java应用设置安全哨兵。

[10]

Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译为体系结构中立的字节码格式（后缀为class的文件），然后可以在实现这个Java平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。

[10]

Java语言是可移植的。这种可移植性来源于体系结构中立性，另外，Java还严格规定了各个基本数据类型的长度。Java系统本身也具有很强的可移植性，Java编译器是用Java实现的，Java

第 2 页共 80 页

陕西理工学院毕业设计

的运行环境是用ANSIC实现的。

[10]

Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式，然后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。

[10]

Java是性能略高的。与那些解释型的高级脚本语言相比，Java的性能还是较优的。

[10]

Java语言是原生支持多线程的。在Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable)的构造子将一个实现了Runnable接口的对象包装成一个线程，其二，从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的是Thread类已经实现了Runnable接口，因此，任何一个线程均有它的run方法，而run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。Java语言支持多个线程的同时执行，并提供多线程之间的同步机制（关键字为synchronized）。

[10]

Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。

Java语言的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。

(2) JDK运行环境

[8]

JDK(Java Development Kit) 是 Java 语言的软件开发工具包(SDK)。SE(J2SE)，standard edition，标准版，是我们通常用的一个版本，从JDK 5.0开始，改名为Java SE。EE(J2EE)，enterprise edition，企业版，使用这种JDK开发J2EE应用程序，从JDK 5.0开始，改名为Java EE。ME(J2ME)，micro edition，主要用于移动设备、嵌入式设备上的java应用程序，从JDK 5.0开始，改名为Java ME。

没有JDK的话，无法编译Java程序，如果想只运行Java程序，要确保已安装相应的JRE。JDK包含的基本组件包括：

javac – 编译器，将源程序转成字节码。

jar – 打包工具，将相关的类文件打包成一个文件。 javadoc – 文档生成器，从源码注释中提取文档。 jdb – debugger，查错工具。

java – 运行编译后的java程序（.class后缀的）。

appletviewer：小程序浏览器，一种执行HTML文件上的Java小程序的Java浏览器。 Javah：产生可以调用Java过程的C过程，或建立能被Java程序调用的C过程的头文件。 Javap：Java反汇编器，显示编译类文件中的可访问功能和数据，同时显示字节代码含义。 Jconsole: Java进行系统调试和监控的工具。 (3) MyEclipse开发工具

MyEclipse企业级工作平台（MyEclipseEnterprise Workbench ，简称MyEclipse）是对EclipseIDE的扩展，利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的JavaEE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate。MyEclipse 是一个十分优秀的用于开发Java, J2EE的 Eclipse 插件集合，MyEclipse的功能非常强大，支持也十分广泛，尤其是对各种开源产品的支持十分不错。MyEclipse目前支持Java Servlet,AJAX, JSP, JSF, Struts,Spring, Hibernate,EJB3,JDBC数据库链接工具等多项功能。可以说MyEclipse是几乎囊括了目前所有主流开源产品的专属eclipse开发工具。根据官方最新消息，MyEclipse 2013

第 3 页共 80 页

陕西理工学院毕业设计

已经正式发布！MyEclipse 2013[2]支持HTML5、JQuery和主流的Javascript 库。随着MyEclipse 2013支持Html5，你可以添加音频、视频和API元素到你的项目，从而为移动设备创建复杂的Web应用程序。你甚至还可以通过HTML5 可视化设计器设计令人难以置信的用户界面。同时，随着MyEclipse 2013支持JQuery，你可以通过插件提升性能，并添加动画效果到设计中。

第 4 页共 80 页

陕西理工学院毕业设计

2排序算法

2.1直接插入排序

(1) 基本原理

假设待排序的n个记录{L0，L1，?，Ln}顺序存放在数组中，直接插入法在插入记录Li(i=1，2，?，n-1)时，记录被划分为两个区间[L0,Li-1]和[Li+1,Ln-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，?，K0依次比较，找出应该插入的位置，将记录Li插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止，为了在查找插

[1]

入位置的过程中避免数组下标出界，在l[0]处设置监视哨。排序示例见图2.1。

图2.1 直接插入排序示例

(2) 算法描述

对字符串顺序链表src作直接插入排序,返回值为空。 public void insertSort(String[] src) { for (int i = 2; i < src.length; i++) { if (src[i].compareTo(src[i - 1]) < 0) { src[0] = src[i]; src[i] = src[i - 1]; int j = i - 2; for (; src[0].compareTo(src[j]) < 0; j--) { src[j + 1] = src[j]; } src[j + 1] = src[0]; } } }

(3) 时间复杂度分析

第 5 页共 80 页

陕西理工学院毕业设计

直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复

杂度为O(n)。 2.2折半插入排序

(1) 基本思想

是对直接插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度[2]。

(2) 算法描述

对字符串顺序链表src作折半插入排序,返回值为空。 public void binaryInsertionSort(String[] src) { for (int i = 2; i < src.length; i++) { // 将src[i]暂存在src[0] src[0] = src[i]; int low = 1, high = i - 1; while (low <= high) { int m = (low + high) / 2; if (src[0].compareTo(src[m]) < 0) {// high = m - 1; } else { low = m + 1; } } // 记录后移 for (int j = i - 1; j >= high + 1; j--) { src[j + 1] = src[j]; } // 插入 src[high + 1] = src[0]; } }

(3)时间空间复杂度

折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。附加空间O(1); 2.3快速排序

(1) 基本原理

对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小则可分别对两部分记录继续进行排序，以达到整个序列有序。假设待排序的序列为{ K.r[s],K.r[s+1],...,K.r[t]},首先任意选取一个记录（通常选第一个）作为支点，然后按下述原则重新排列其余记录：将所有关键字比它小的记录都安置在它的位置之前，将所有关键字较它打的记录都安置在它的位置之后。由此可以将位置i作分界线，将序列{ K.r[s],K.r[s+1],...,K.r[t]}分割成两个子序列{ K.r[s],K.r[s+1],...,K.r[i-1]}和

[11]

{ K.r[i+1],K.r[s+1],...,K.r[t]}。这个过程称一趟快速排序。排序示例见图2.2。

第 6 页共 80 页

陕西理工学院毕业设计

图2.2 快速排序示例

(2) 算法描述

交换顺序表L中子表l[low...high]的记录，枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它。

public int partition(String[] l,int low,int high) { //用字表的第一个记录轴的记录 l[0] = l[low]; //轴记录关键字 String pivotkey = l[low]; //从表的两端交替向中间扫描 while(low < high) { //将比轴记录小的记录移到低端 while(low < high && l[high].compareTo(pivotkey) >= 0) { --high; } //将比轴记录大的记录移到高端 l[low] = l[high]; while(low

第 7 页共 80 页

陕西理工学院毕业设计

//轴记录到位 l[low] = l[0]; //返回轴的位置 return low; }

(3) 时间复杂度分析

如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，

此时，快速排序效率最低，其最坏情况时间复杂度为O(n)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。 2.4选择排序

(1) 基本原理

待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，

[12]

依次类推直到所有记录。排序示例见图2.3。

图2.3 选择排序示例

(2)算法描述

对字符串顺序链表src作选择排序，返回值为空。 public void selectSort(String[] src){ for (int i = 0; i < src.length; i++) { int j = selectMinKey(src, i); if (j != i) { String temp = src[i]; src[i] = src[j]; src[j] = temp; }}

}

(3)时间复杂度分析

该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况

的时间复杂度都为O(n)。

第 8 页共 80 页

陕西理工学院毕业设计

3系统设计

3.1系统模块结构

根据需求分析，按功能划分8个模块，分别是：链表插入排序模块、直接插入排序模块、折半插入排序模块、选择排序模块、归并排序模块、堆排序模块、基数排序模块。排序算法动态演示系统功能模块结构图如图3.1所示。

排序算法动态演示系统

链直折交选归堆

表接半换择并排