排序算法的实现和比较VC++
毕业论文
排序算法的实现和比较
摘 要：
排序是计算机程序设计中的1种重要操作，其功能是对1个数据元素集合或序列重新排列成1个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序排列的。如有序表的折半查找，查找效率较高。还有，2叉排序树、B-树和B+树的`构造过程就是1个排序过程。
排序世界这个程序分为4个模块.排序模块将多种不同的排序算法集成在1个界面里，对各种综合排序算法的复杂度进行研究，对比其时间及空间复杂度，发现它们各自的特点；复杂度模块将排序算法的复杂度集成在1个界面，可以对理论上的复杂度进行研究；模型模块是用动态的方法把排序过程表现出来；综合模块可以多次排序并比较时间空间复杂度。
关键词：图灵机；时间复杂度；空间复杂度；排序算法。
The implementation and comparison of sorting arithmetic
Abstract：
The management, whose function is sorting a data element collection or sequence to another sequence according to some value of a data，is a kind of important operation in computer programming。Data items used as sorting according，which is called "the arrangement code", is also key code of data element. In order to be more convenient for searching, it is usually hoped that the data sheet in the computer is sorted as key code sequence。For example, the half-searching of sequence list is of higher efficiency. And the performing of two forks sequence tree, B- tree and B+ trees is such a process。
The program, sort world, is divided into four modules。Many kinds of different arrangement algorithm are integrated in a surface by sort module。It also does research on the complexity of every kind of synthesis sort algorithm。Respective characteristic can be found from the contrast between time and space complexity。 The model module displays the arrangement process through moving surfaces。Meanwhile, the whole module can be sorted and compared in complexity of time and space many times。
Keywords：Turing machine; Time complexity; Space complexity; Sorting arithmetic.
目录
前 言 1
1 绪 论 2
1.1课题背景 2
1.2研究意义 2
1.3课题任务 2
1.4开发工具 3
2 排序算法简介 4
2.1算法理论 4
2.2排序理论 5
2.3排序算法与图灵机 6
3 需求说明 7
3.1任务概述 7
3.1.1目标 7
3.1.2 约束 7
3.2对性能的规定 7
3.2.1精度 7
3.2.2时间特性要求 7
3.3输人输出要求 7
3.4设备 7
4 概要设计 8
4.1设计思路 8
4.2程序流程图 8
4.2.1 模块图 8
4.2.2 Sort模块 9
4.2.3 Airth模块 11
4.2.4 Mode模块 11
4.3排序算法的具体模型 13
4.3.1 交换排序 13
4.3.2选择排序 13
4.3.3 直接插入排序 13
4.3.4 2分插入排序 17
4.3.5 Shell排序 17
4.3.6 冒泡排序 17
4.4程序模块主要函数 21
4.4.1 Sort模块函数 21
4.4.2 Airth模块函数 21
4.4.3 Mode模块函数 21
4.5 程序界面 22
4.5.1 主界面 22
4.5.2 复杂度界面 22
4.5.3 排序界面 23
4.5.4 模型界面 24
4.5.5统计界面 24
5 详细设计 26
5.1 SORT函数模块 26
5.1.1 产生随机数模块 26
5.1.2 排序模块 26
5.1.3 时间消耗模块 28
5.2 AIRTH模块 28
5.2.1 初始化模块 28
5.2.2 排序模块 28
5.2.3 综合模块 29
5.3 排序模型模块 29
5.3.1 分配数模块 29
5.3.2 创建数模块 29
5.3.3 集合模块 29
5.3.4 排序模型 29
6 软件测试及误差分析 31
6.1 软件测试项目 31
6.1.1 程序常规测试 31
6.1.2 程序稳定性测试 31
6.1.3 系统的兼容性测试 31
6.2 测试结果 31
6.2.1 程序常规测试结果 31
6.2.2 程序稳定性测试结果 31
6.2.3 系统的兼容性测试结果 31
6.3 排序算法误差分析 32
6.3.1 插入排序算法误差分析 32
6.3.2 希尔排序算法误差分析 33
6.3.3 冒泡排序算法误差分析 33
6.3.4 选择排序算法误差分析 33
6.3.5 堆排序算法误差分析 34
6.3.6 快速排序算法误差分析 34
6.3.7 归并排序算法误差分析 35
6.3.8 2分插入排序算法误差分析 35
6.3.9 交换排序算法误差分析 35
7 结束语 36
参考文献 37
致谢 38
前言
排序是指输入1个序列，而按1定规律输出原序列的1个重排。对我们来说，用得最多的是升序排序，即对1个输入序列<a1、a2、…、an>产生的输出的序列<a1’、a2’、…、an’>保证a1’< a2’<…< an’。排序算法有很广泛的应用，在我们的计算机上几乎无时无处不存在。因为无处不在，所以我们必须研究排序的算法。比较它在不同情况下的优劣，对计算机科学的发展有重要作用。
我们要排序的元素可以是1个简单的整数，1个字符或是1个字符串，也可以是1个复杂的数据结构，拥有很多域，但它必须至少有1个key域，我们正是针对这个key域进行排序（本文中主要研究的是长整型的数的排序过程）。除了在随机排序算法中，我们都要求不管key域是什么类型，至少它应该支持比较操作，即能判断两个元素key域之间的大小关系。
研究排序主要方法：计算排序算法的时间空间复杂度(最坏, 平均和最佳)及算法的稳定性。
本设计主要解决的问题是：比较排序算法的时间空间复杂度以及排序算法的动态实现。
【排序算法的实现和比较VC++】相关文章：