导航:首页 > 源码编译 > 算法研究与设计

算法研究与设计

发布时间:2023-11-08 05:35:34

‘壹’ 编写冒泡排序算法 冒泡排序算法的分析与改进 算法设计

冒泡排序算法的分析与改进

孙伟

(安徽中医学院 医药信息工程学院 09医软一班,安徽合肥,230009)

摘 要: 冒泡排序算法有两个优点:1“编程复杂度”很低,很容易写出代码;2. 具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,但当需要排序的数据较多且无序时,冒泡排序算法的时间复杂度较大,比较次数较多,本文提出了一种冒泡排序算法的改进方法,可以大大减少比较的次数,降低算法的时间复杂度。 关键让握坦词:交坦桐换排序 扫描 稳定 算法 中图分类号:TU 411.01 文献标识码:A

Bubble sort algorithm analysis and improvement

SUN Wei

(Anhui University of Traditional Chinese Medicine Medical Information Engineering, Hefei 230009, China ;)

Abstract: Bubble sort algorithm has two advantages:1 “Programming complexity”is very low,and it is easy to write code;2.It has the stability, the stability refers to the original sequence in the same element relative sequence remains to sort sequence, but when the need to sort the data and more disordered, bubble sort algorithm time complexity compared to larger, more often, this paper presents a bubble sort algorithm method, can greatly rece the number of comparisons, rece the time complexity of algorithm.

Key words:Exchange sort ; Scanning ; stability ; Algorithm

1. 概述

1.1 冒泡排序简介

冒泡排序法是一种交换排序法皮腊,这种方法的基本思想是,将待排序

的元素看作是竖着排列的“ 气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“ 气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“ 轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“ 最轻”的元素就浮到了最高位置;处理二遍之后,“ 次轻”的元素就浮到了次高位置。在作第二遍处理时,由于

最高位置上的元素已是“ 最轻”元素,所以不必检查。一般地,第i 遍处理时,不必检查第i 高位置以上的元素,因为经过前面i- 1遍的处理,它们已正确地排好序。

1.2 冒泡排序方法

冒泡排序法是一种最简单的排序算法, 它和气泡从水中往上冒的情况有些类似。其基本算法如下:对1 至n 个记录,先将第n 个和第n- 1 个记录的键值进行比较,如r [n].key

——————————————————————————————————————————————————————— 收稿日期:2012-4-14;

作者简介:孙伟 1992-10-04 女 09713033 09医软一班

实现的功能:将键值最小的记录传到了第1 位。然后,再对2 至n 个记录进行同样操作,则具有次小键值的记录被安置在第2 位上。重复以上过程, 每次的移动都向最终排序的目标前进,直至没有记录需要交换为止。具体实现时,可以用一支旗子flag 表示第i 趟是否出现交换。如果第i 趟没有交换,则表示此时已完成排序,因而可以终止。

1.3 冒泡排序过程示例

设待排序的键值为: 25 17 65 13 94 47 41 94

执行冒泡排序的过程如下图所示。其中,第一列为初始键值序列, 第二列至第八列依次为各趟排序的结果, 图中用方括号括起来的是当前待排序的无序区。

每一次排序都使有序区扩充了一个气泡,在经过i 次排序之后,有序区中就有i 个气泡, 而无序区中气泡的重量总是大于等于有序区中气泡的重量,整个冒泡排序过程至多需要进行n- 1 次排序。但是, 若在某一次排序中未发现气泡位置的交换, 则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则因此冒泡排序过程可在此次排序后终止。在上图的示例中,在第四次(图中第五列) 排序过程中就没有气泡交换位置, 此时整个文件已达到有序状态。为此,实际给出的算法中, 我们可以引入一个布尔量flag , 在每一次排序之前, 先将它置为true ,若在一次排序中交换了记录, 则将它置为false 。当一次排序结束时,我们再检查flag ,若未曾交换过记录便终止算法。

该算法的时间复杂性为0(n2), 算法为稳定的排序方法。

2. 对于冒泡算法的改进

2.1 第一种改进方法

如果在某一趟循环中没有任何数据交换发生, 则表明数据已经排序完毕。那么剩余的循环就不需要再执行假设需要排序的数据已经按照从小到大排列,那么第一趟比较就不会有任何数据交换发生。这种改进算法如下:

设置一个标志位,当没有交换的时候这个标志位不会变化,那么说明数据已经排序好了,就不需要再进行剩余的循环。只有在标志位被重新设置的情况下才会进行剩余的循环。

public static

void ImproveBubble1(int [ ]myArray) {

bool isSorted = false;

for(int i = 0; i

// 只有在没有排序的情况下才继续循环 { isSorted =

true; // 设定排序标志

for(int j = 0; j

myArray[j+1] ) { isSorted =

false; // 如果是没有排序,就重新设定标志 Swap(refmyArray, refmyArray[i+1]);

} } } }

从这种算法可以看出,若记录的初始状态是正序( 从小到大) 的,则一趟扫描即可完成排序。所需的较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n);若初始记录是反序( 从大到小) 的,则需要进行n- 1 趟排序,每趟排序要进行n- i 次关键字的比较,且每次比较都必须移记录三次来达到交换记录位置。在这情况下比较和移动次数达到最大值:比较次数:Cmax= n(n- 1)/2 移动次数: Mmax=3n(n- 1)/2因此这种改进方法的最坏时间复杂度也为0(n^2)。在平均情况下,算法可能在中间的某一趟排序完后就终止,但总的比较次数仍为0(n^2),所以算法的

平均时间复杂度为0(n^2)。因此,这种算法最好的时间复杂度为0(n)。平均,最坏时刻复杂度为0(n^2)。

2.2 第二种改进方法

在冒泡排序的每趟扫描中, 记住最后一次交换发生的位置lastexchange 也能有所帮助。因为该位置之前的相邻记录已经有序,故下一趟排序开始的时候,0 到lastexchange 已经是有序的了,lastexchange 到n- 1是无序区。所以一趟排序可能使当前有序区扩充多个记录。即较大缩小无序区范围,而非递减1,以此减少排序趟数。这种算法如下:

在冒泡排序中,每趟排序实现了将最大(升序) 或最小(降序) 的记录安置到未排序部分的最后位置,即最终位置。通过进一步观察研究,由于每趟排序过程中,通过和邻记录关键字两两比较,大(升序) 或小(降序) 的记录在不断地往下沉或往后靠,小(升序) 或大(降序) 的记录在不断往上冒或往前靠。每经过一趟排序,在最后次交换位置后面的记录都已经排好序。根据上面的思路,对n 个记录进行第k 趟排序,首先需在第k- 1 趟排序时记下最后交换的位置。然后在第k 趟排序时,将第一个记录的关键字与第二个记录的关键字进行比较,符合交换条件时,进行交换。再比较第二个记录和第三个记录的关键字,依次类推,直至第m- 1 个记录和第m 个记录的关键字进行比较,而不需要比较至n- k- 1 个记录。在大部分排序中,m 都小于n- k- 1从而减少了比较趟数和每趟的比较次数。由于在第一趟排序

时,没有上一趟排序的m 值。因此,还要设置m 的初始值为n- 1。

public static

void ImproveBubble2(int[ ]myArray) { int m= myArray.Length -1; int k, j; while(m> 0 )

{ for( k=j=0; j myArray[j+1]) {

Swap(refmyArray[j], refmyArray[j+1]);

k = j; // 记录每次交换的位置 }}

m= k; // 记录最后一个交换的位置 }}

从这种算法可以看出,若记录的初始状态是正序( 从小到大) 的。则一趟扫描即可完成排序, 所的关键比较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n);若初始记录是反序( 从大到小) 的,则需要进行n- 1 趟排序,每趟排序要进行n- i 次关键字的比较,且每次比较都须移动记录三次来达到交换记录位置。在这情况下比较和移动次数达到最大值:比较次数:Cmax= n(n- 1)/2 移动次数Mmax=3n(n- 1)/2因此,这种办法的最坏时间复杂度也为0(n^2)。在平均情况下,算法较大地改变了无序区的范围,从而减少了比较的次数,但总的比较次数仍为0(n^2)。所以算法的平均时间复杂度为0(n^2)。因此,算法2 最好的时间复杂度为0(n)。平均,最坏时刻复杂度为0(n^2)。 2.3 双向扫描冒泡法

若记录的初始状态为:只有最轻的气泡位于d[n]的位置(或者最重的气泡位于d[0]位置) ,其余的气泡均已排好序。在上述三种算法中都要做n- 1 趟扫描。实际上只需一趟扫描就可以完成排序。所以对于这种不

对称的情况。可对冒泡排序又作一次改进。在排序过程中交替改变扫描方向。即先从下扫到上,再从上扫到下,来回地进行扫描,这样就得到双向冒泡排序算法。

对n 个记录进行排序时,设up 记录了从前面向后面依次进行扫描时最后的交换位置,low 记录了从后面向前面依次进行扫描时最前的交换位置。由上个改进的冒泡排序的原理可知,up 后面的记录和low 前面的记录都已有序。每趟排序都由两次不同方向的比较、交换组成。第一次是从未排好序的第一个记录开始,即从low 记录开始,向后依次两两比较,如果不符合条件,则交换之,

直至比较到未排好序的最后一个记录,即up 记录为止。同时记下最后一次交换的位置,并存于up 。第二次是从未排好序的最后一个记录开始, 即从up 记录开始,向前依次两两比较,如果不符合条件,则交换之,直至比较到未排好序的第一个记

录,即low 记录为止。同时记下最后次交换的位置,并存于low 。这样,就完成了一趟排序。每趟排序都实现了将未排好序部分的关键字大的记录往后移

(升序) ,

关键字小的记录往前移( 升序) ,从而使

两端已排好序( 如果是降序,记录移动的方向则相反) 。未排好序部分的记录的首尾位置分别由low 和up 指明。不断按上面的方法进行排序,使两端已排好序的记录不断增多,未排好序部分的记录逐渐减少。即low 和up 的值不断接近,当low>=up 时,表明已没有未排好序的记录,排序就完成了。由于在第一趟排序时,没有上趟排序的low 和up 值。因此,还要设置low 和up 的初始值分别为0 和n- 1。

public static

void ImproveBubble3(int [ ]myArray) { int low, up, index, i; low= 0;

up = myArray.Length - 1; index = low; while( up > low)

{ for( i=low; imyArray[i+1]) {

Swap(refmyArray, refmyArray[i+1]); index = i; }}

up= index; // 记录最后一个交换的位置

for(i=up; i>low; i- - ) // 从最后一个交换

位置处从下向上扫描

{ if(myArray

Swap(refmyArray, refmyArray[i- 1]); index = i;

}} low= index; // 记录最后一个交换的位



}}

从这种算法可以看出,若记录的初始状态是正

序( 从小到大) 的,则一趟扫描即可完成排序。所需的关键比较和记录移动的次数分别达到最小值n- 1 和0。即算法最好的时间复杂度为0(n);若初始记录是反序( 从大到小) 的,则需要进行[n/2]趟排序。如果只有最重的气泡在最上面( 或者最轻的气泡在最下面) ,其余的有序,这时候就只需要比较1 趟。但是在最坏的情况下,算法的复杂度也为0(n^2)。因此,算法最好的时间复杂度为0(n),最坏时刻复杂度为0(n^2)。

3. 性能分析

为了分析数据两种冒泡排序法的性能, 我们用自编的测试程序对大量数据进行了测试,得出下表,从表中可以直观地看出两种冒泡排序方法的性能差异( 时间单位为毫秒)。

图1 算法运行时间比较表

4. 结束语

从上面的表格可以看出,在数据量比较小的时候,这几种算法基本没有任何区别。当数据量比较大的时候,双向扫描冒泡排序会有更好的效率。但是效率并没有根本的提升。因此冒泡排序确实不是我们排序的首选。在数据量比较大的时候,快速排序等会有非常明显的优势。但是在数据量很小的时候,各种排序算法的效率差别并不是很大。那么冒泡排序也会有自己的用武之地。因此,在实际考虑算法的时候,最重要的是熟悉各种算法的性能表现并且根据数据的数量以及当前运行的环境,开发的进度选择最合适的算法。

[参 考 文 献]

[1]( 美) 莱维丁着. 潘彦译,《算法设计与分析基础》. 清华大学出版社 [2] 胡金初,《计算机算法》. 清华大学出版社

[3] 阿苏外耶(M.H.Alsuwaiyel),朱洪(译),《算法设计技巧与分析》.电子工业出版社 [4](美)Robert sedgewick,《算法分析导论》.机械工业出版社

[5]( 美)Michael T.Goodrich Roberto Tamassia,《算法分析与设计》人民邮电出版社 [6]王晓东,《计算机算法设计与分析》电子工业出版社

[7]Shaffer,Clifford,张铭,《数据结构与算法分析》电子工业出版社 [8]刘任任 ,《算法设计与分析》武汉理工大学出版社,2003

‘贰’ 学习算法分析与设计需要那些基础(是否需要学习离散数学和线性代数)

算法分析与设计,目前国内本科生和硕士生的教材好像都是从国外翻译过来的。听起来挺复杂的样子,如果简单地掌握和运用还是不难的,大部分内容在数据结构中都涉及过,实际编程中也运用比较多,难的在于算法的理论研究,如21世纪的七大难题之一的NP问题就是算法问题(涉及逻辑可满足性问题)。

简单地讲需要的基础有以下几类:
1、基础类(相对一般本科生而言):(1)把数据结构学好了算法就不难的,而数据结构其实就是图论的运用,如果是非数学专业的学生可以看离散数学中的图论部分。(2)算法分析设计时间和空间复杂度的计算,常用的还是毛泽东的战略思想——以空间换取时间。所以要学会简单的数量级运算,涉及部分代数式和数论的知识。只要简单掌握运算就可以了,不必深究。
2、提高型(研究生水平):图论、组合数学、数理逻辑学要专门学习,可以采用数学系本科生的图论、组合数学、数理逻辑学等专业课的教材。其中组合数学中的组合设计在一定程度上和算法设计有异曲同工之处。
3、研究型(专业研究):这主要看自己的研究方向了,如果研究能力强的话可以在很短时间内可以把需要遇到的数学知识搞懂,没有现成的固定模式。其中如研究NP问题,需要非常精深的逻辑学知识和数论基础。但不管哪个研究方向,数学的缜密思维和推理能力都是必备的,这不是一朝一夕可以练就的,需要长时间的锻炼。

以上仅个人一点点体会,仅供参考。

‘叁’ 编译原理和算法分析与设计哪个更难

编译原理和算法分析与设计相比,算法分析与设计更难。

算法分析的话比较偏重整数规划,数列的求解,组合数学等等,设计那就要靠悟性了,而且要见多识广,不管你使用的是什么语言,也不管语言怎么发展,数据结构是变不了多少的。算法设计也差不多,帮助你改善解决问题的思维。

算法分析与设计的内容:

算法设计与分析是整个CS课程体系当中最为重要的几门课程之一,因为这门课是现代计算机科学发展的核心课程,和离散数学、数理逻辑四论地位相当,号称必修中的必修,不过一般CS系不需要学数理逻辑四论,国内大学的四论教学开展的也不多。因此请大家一定要在这门课打好基础,学好这门课能让你未来的工作和学习非常轻松。

‘肆’ 《算法分析与设计》课程讲什么内容

《算法分析与设计》课程是理论性与应用性并重的专业课程。本课程以算法设计策略为知识单元,系统地介绍计算机算法的设计方法和分析技巧。课程教学主要内容包括:第一章,算法概述;第二章,递归与分治策略;第三章,动态规划;第四章,贪心算法;第五章,回溯法;第六章,分支限界法。通过介绍经典以及实用算法让同学掌握算法设计的基本方法。结合实例分析,让同学深入理解算法设计的技巧,以及分析算法的能力。

‘伍’ 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

对于,大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题,首先要来聊聊他们的联系:1、都是一种推导算法;2、将它们分解为子问题求解,它们都需要有最优子结构。这两个特征师门的联系。

拓展资料:

贪婪算法是指在解决问题时,它总是在当前做出最佳选择。也就是说,在不考虑全局优化的情况下,该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。

动态规划是运筹学的一个分支,是解决决策过程优化的过程。20世纪50年代初,美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时,提出了着名的最优化原理,建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用,在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显着的成果。

阅读全文

与算法研究与设计相关的资料

热点内容
反诈骗app怎么找回密码 浏览:631
java方法和函数 浏览:418
程序员衣服穿反 浏览:959
java多类继承 浏览:157
怎么用多玩我的世界连接服务器地址 浏览:483
为什么华为手机比安卓流畅 浏览:175
javamap多线程 浏览:226
卡西欧app怎么改时间 浏览:843
jquery压缩图片 浏览:970
用纸筒做解压东西 浏览:236
神奇宝贝服务器如何tp 浏览:242
云服务器支持退货吗 浏览:277
贷款等额本息算法 浏览:190
根服务器地址配置 浏览:499
单片机是软件还是硬件 浏览:624
vivo手机怎么看编译编号 浏览:320
塑钢扣条算法 浏览:301
linux应用程序安装 浏览:414
linux怎么查找命令 浏览:431
安卓12原生和非原生是什么意思 浏览:277