对数据进行排序有可能是检索数据的一个初始步骤。由于排序非常重要而且可能非常耗时,所以它已经成为了计算机科学中广泛研究的课题,而且计算机界的先辈们、前辈们早已经研究出了一些非常成熟的方法。
冒泡排序算法运行起来非常慢,但是在理解上却是最简单的,因此大部分的教材中,冒泡算法一般都是第一个接触的算法,以便于大家理解,我这里也不例外。
为了讲清楚冒泡排序的整个过程,我们不妨思考下那经典的“高矮排队
”的问题。每个人的记忆中都有这样的情景,体育课或者体操的时候,都会按照高矮排队。我个头不算高,因此大部分的时候都很“有幸”的成为队伍的前几个。假设有10个人排列成一队,现在需要按身高从低到高为他们排队,该怎么办呢?
我们可以同时看到所有的人,并且可以用肉眼观察立刻找出最高的一个,经过这样一系列的比较和调整,就可以毫不费力的给他们排队。计算机则没有我们这么聪明。因为计算机只能根据“比较”操作原理,对所有的人员进行排序,因此计算机每次只能看到两个人。
过程如下:从队列最左边(实际上任何一个方向都可以)开始,比较0号位置和1号位置的人。如果左边的人(0号)高,就让两个人交换(只有这样才能相邻的两个人中,左边的永远比右边的矮)。如果右边的人高,就什么也不做。然后右移一个位置,比较1号和2号位置的人,和刚才一样。再次过程当中,我们可以看到执行的步骤:
1、 比较两个人的身高
2、 如果左边的人高些,则交换两个人的位置
3、 向右移动一个位置,比较下面的两个人
沿着这个队列按照以上的方法比较下去,一直比较到队列的最右端。此时,虽然还没有排序完成,但是最高的那个人已经被排到了最右边了。这也正是这个算法被成为冒泡排序算法的原因:因此在算法执行的时候,最大的数据项总是“冒泡”到数组的最右边(或最上边)。
按照这样的思路,我们写出如下的程序
:
public void bubbleSort() {
int outterLoop,innerLoop;
double temp;
for(outterLoop=elementCount-1;outterLoop>1;outterLoop--) {
for(innerLoop=0;innerLoop<outterLoop;innerLoop++) {
if(array[innerLoop] > array[innerLoop+1]) {
//swap them
temp = array[innerLoop+1];
array[innerLoop+1] = array[innerLoop];
array[innerLoop] = temp;
}//end of if
}//end of for
}//end of for
}//end of method bubbleSort()
说明:
这个算法的思路是要将最小的数据项放在数组的最开始,并将最大的数据项放在数组的最后。外层for循环从数组的最后开始,每经过一次循环outterLoop减一。下标大于outterLoop的数据项都已经是排好序的了。也就是说,外层循环每循环一次,总可以保证序列中最大的数据项已经被移动到了最右端,因此outterLoop每次可以减一以减少不必要的比较。
内存for循环从数组的最开始算起,每完成一次内部循环体就加一。在内层循环中,数组下标而innerLoop和innerLoop+1位置的两个数据项进行比较,如果下标为innerLoop的数据项大于innerLoop+1的数据项,则交换两个数据项。简单来说,两个人站在一起比高低,如果左边的比右边的高,那么给两个人换位置,依次比较下去即可。实际上,交换的过程可以单独写成另外一个方法在这里调用,但是这样做反而加大了系统的开销,因此直接在这里做了交换。
效率问题:
做一个简单的类推,如果待操作的数据项有10个,那么第一次循环需要比较的次数是9次,第二次比较的次数是8次,依次类推:9+8+7+6+5+4+3+2+1=45次。对于N的数据项,需要比较的次数:
(N-1)+ (N-2)+ (N-3)+……+1 = N*(N-1)/2
这样,算法做了大概N*N/2次比较(忽略减1,当数据量很大时不会有很大的差别)。比较的次数和交换的次数都和N的平方成正比,因此使用大O表示法来说:冒泡排序运行需要O(N*N)时间级别。
完整程序如下:
package barry.sort;
public class BubbleSorter {
private double[] array;
private int elementCount;
public BubbleSorter(int size) {
array = new double[size];
elementCount = 0;
}//end of constructor
public void insert(double value) {
array[elementCount] = value;
elementCount++;
}//end of method insert()
public void display() {
for(int i=0;i<elementCount;i++) {
System.out.print(array[i]+"\t");
}//end of for
}//end of method display()
public void bubbleSort() {
int outterLoop,innerLoop;
double temp;
for(outterLoop=elementCount-1;outterLoop>1;outterLoop--) {
for(innerLoop=0;innerLoop<outterLoop;innerLoop++) {
if(array[innerLoop] > array[innerLoop+1]) {
//swap them
temp = array[innerLoop+1];
array[innerLoop+1] = array[innerLoop];
array[innerLoop] = temp;
}//end of if
}//end of for
}//end of for
}//end of method bubbleSort()
}
package barry.sort;
public class BubbleSorterApp {
public static void main(String[] args) {
BubbleSorter sorter = new BubbleSorter(10);
sorter.insert(-10);sorter.insert(56);
sorter.insert(23);sorter.insert(8723);
sorter.insert(-90);sorter.insert(993);
sorter.insert(33);sorter.insert(-373);
//display them before sort
System.out.println("\nBefore Sort:");
sorter.display();
//sort them
sorter.bubbleSort();
//display tem after sort
System.out.println("\nAfter Sort:");
sorter.display();
}
}
学习和交流活动,望请大家多多指点。
分享到:
相关推荐
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
数据结构排序算法中的冒泡排序,是我们学院学习计算机语言室接触到的第一个算法,可以说是最基础的一个排序算法
数据结构与算法之冒泡排序pta:基于C语言的编程实践与测试 数据结构与算法之冒泡...本资源适合算法教学和学习的教师和学生使用,帮助他们通过视频和代码来观看和学习冒泡排序pta的分析和讲解,提高算法的兴趣和能力。
实现直接插入排序、折半插入、冒泡、快速、直接选择、堆、归并排序算法。比较各种 算法的运行速度和时间复杂度,是否为稳定排序。分析每一趟排序结果。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
本资源包含《数据结构》考研的九种内部排序算法考点的算法代码及排序过程图示,以表格、图文方式详细讲解每一种排序算法的排序过程。 包含的九种内部排序有:直接插入排序、折半排序、希尔排序、冒泡排序、快速排序...
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
数据结构-3期(KC002) 冒泡排序算法.docx 学习资料 复习资料 教学资源
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
第1章 课程导学对课程整体进行介绍,让您切实感受到前端工程师学习数据结构与算法的必要性。 1-1 课程导学 试看 1-2 学习姿势 1-3 说明与承诺第2章 基础算法之“字符串类”字符串作为JS最基本的数据类型,掌握好字符...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
南昌大学科学技术学院实验报告,《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程...目的:学习数据结构课程,旨在使学生学会分析研究数据对象的特性,学会数据的组织方法
在学习计算机科学、数据结构或算法的课程中,您可能会遇到冒泡排序算法。本资源可以帮助您深入理解这一算法的实现原理,提高您的编程技能,并加深对C语言的理解。此外,掌握冒泡排序算法对于准备参加编程竞赛或日常...