冒泡排序的分析改进算法

《冒泡排序的分析改进算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn冒泡排序的分析改进算法杨义磊甘肃农业大学计算机科学与技术学院，兰州（730070）Email：mailto:yangyilei001@126.com摘要：排序算法对于计算机信息处理很重要,一个好的排序不仅可以使信息查找的效率提高,而且还直接影响着计算机的工作效率。目前排序领域许多最简单的算法都是基于冒泡排序算法,本文对冒泡排序的基本原理进行了介绍和分析,对算法性能进行了比较,并给出了相应的改进算法.关键词：排序算法，冒泡排序，算法分析，算法时间复杂度1.引言排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新

2、排列成一个按关键字有序的序列.排序是程序设计中非常重要的内容,每一种程序设计语言中都涉及到排序,它的功能是将一组无序的的数据序列变成有序的数据序列,结果一般只有两种情况:数据从大到小排列或者从小到大排列.排列的算法有很多种,常用的有三种,即冒泡排序,选择排序,和插入排序.要判断排序算法的优劣,一般有两个标准:一是算法执行所需要的时间,又称时间复杂度;二是算法所需的存储空间,又称空间复杂度.排序算法的优劣将直接影响到程序的性能.复杂度因排序算法的选择而有所不同,一般可分为三类:(1)简单的排序方法,其复杂度为[1]O(n²);(2)先进的排序方法,其时间复杂度为O(nlogn);(3)基数排

3、序,其时间复杂度为O(d*n).在计算机处理信息的过程中,由于排序数据或记录非常频繁,计算机运行时间的很大部分就被花费在数据或记录的排序上.排序算法对于计算机信息处理很重要,一个好的排序不仅可以使信息查找的效率提高,而且还直接影响着计算机的工作效率。所以排序算法(sortingalgorithm)就成了计算机程序设计中的一个重要环节,同时也成为研究的重要课题。它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字(keyword)排序的序列。在众多的排序方法中,冒泡排序(bubblesort)是最简单的一种,冒泡排序法可以形象的描述为:使较小的值象空气泡一样逐渐”上浮”到数组

4、的顶部,而较大的值逐渐”下沉”到[2]数组的底部.本文主要对冒泡排序算法及其几种改进算法的基本原理进行介绍和分析.2.冒泡排序的基本思想冒泡排序是排序中一种简单的排序方法.它的基本思想是对所有相邻记录关键字值进行比较,使较小的(大)关键字的记录值往上升,这样从上到下执行一遍后,关键最大(小)的记录沉到最底下.在下一遍扫描时,可以不考虑这个关键字最大(小)的记录,而减少一次比较.上述的比较过程反复执行,直到所有的记录不再上升为止.此方法称为下沉(上浮).冒泡排序算法的实现需两重循环,通常采用以下方法:外层循环控制变量(设为i)的变化是从数据比较的趟数考虑的.如:设有n个数据参加排序,需n-1

5、趟比较,i的变化范围是1→n-1;而其内层循环控制变量(设为j)的变化范围为0→n-i-1(C语言中数组[3]元素下标从0开始).3.冒泡排序的过程冒泡排序的过程很简单.首先将第一个记录的关键字和第二个记录的关键字进行比-1-http://www.paper.edu.cn较,若为逆序(即L.r[1].key>L.r[2].key),则将两个记录交换之,然后比较第二个记录和第三个记录的关键字.依次类推,直至第n-1个记录和第n个记录的关键字进行过比较为止.上述过程称做第一趟起泡排序,其结果使得关键字最大的记录被安置到最后一个记录的位置上.然后进行第二趟起泡排序,对前n-1个记录进行同样操作,

6、其结果是关键字次大的记录被安置到第n-1个记录的位置上.一般地,第i趟起泡排序是从L.r[1]到L.r[n-i+1]依次比较相邻两个记录的关键字,并在”逆序”时交换相邻记录,其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1个位置上.整个排序过程需进行k(1≤k

7、91327276565651327383897761327494976132749¯49¯132749¯652749¯7649¯97初第第第第第第始一二三四五六关趟趟趟趟趟趟键排排排排排排字序序序序序序后后后后后后图1起泡排序示例分析起泡排序的效率,容易看出,若初始序列为”正序”序列,则只需进行一趟排序,在排序过程中进行n-1次关键字间的比较,且不移动记录;反之,若初始序列为”逆序”序列,则需进行n-1趟排序,需进行2∑