线性时间选择问题的算法实现及应用.docx

摘要：在算法中选择问题具有非常重要的意义，当面对大量的数据时，选择出对我们有意义的数据，能够提高解决问题的效率。特别是选择出中位数，中位数是一个很有意义的数据，它是统计学中的专有名词。选择问题的算法在很多领域都有应用，例如在统计分析，中值滤波等方面都具有广泛应用。

通常，衡量一个算法的性能指标有多种。例如：时间复杂度，空间复杂度，以及稳定性。本毕业论文主要是从算法的时间复杂度的角度来评判算法的性能，对快速排序选择算法，随机划分选择算法，线性时间选择算法利用Windows程序进行比较分析。并将选择算法运用到中值滤波算法中。演示程序采用Visual studio 2010和Visual C++ 6.0制作完成。

关键词：快速排序选择算法 随机划分选择算法 线性时间选择算法 中值滤波

目录

摘要

Abstract

1.绪论-1

1.1选题研究背景及意义-1

1.2国内外发展研究现状-2

1.3选题研究的主要内容-2

2.线性时间选择问题的引入-2

2.1.选择问题-2

2.2线性时间选择问题-3

3. 选择问题的算法实现-3

3.1 快速排序算法-3

3.1.1算法思路-3

3.1.2算法关键代码-4

3.1.3算法分析-5

3.2基于随机划分的选择算法-6

3.2.1随机算法的意义-6

3.2.2算法思路-6

3.2.3算法关键代码-7

3.2.4算法分析-9

3.3线性时间选择算法-9

3.3.1算法思路-9

3.3.2算法关键代码-10

3.3.3算法分析-12

3.4运行测试-13

4．线性时间选择问题的算法的应用实例-13

4.1中值滤波-13

4.1.1BMP图片存储格式-13

4.1.2中值滤波思想-14

4.1.3中值滤波关键代码-14

4.1.4运行测试-18

5.总结-18

缺陷-19

致谢-20

参考文献-21