对数据进行排序有可能是检索数据的一个初始步骤。由于排序非常重要而且可能非常耗时,所以它已经成为了计算机科学中广泛研究的课题,而且计算机界的先辈们、前辈们早已经研究出了一些非常成熟的方法。
冒泡排序算法运行起来非常慢,但是在理解上却是最简单的,因此大部分的教材中,冒泡算法一般都是第一个接触的算法,以便于大家理解,我这里也不例外。
为了讲清楚冒泡排序的整个过程,我们不妨思考下那经典的“高矮排队
”的问题。每个人的记忆中都有这样的情景,体育课或者体操的时候,都会按照高矮排队。我个头不算高,因此大部分的时候都很“有幸”的成为队伍的前几个。假设有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();
}
}
学习和交流活动,望请大家多多指点。
分享到:
相关推荐
排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序等,解决如何将无序数据变为有序的问题;查找算法如线性查找、二分查找,用于定位数据;图算法如深度优先搜索(DFS)和广度优先搜索(BFS),用于遍历图...
典型的算法包括排序(如冒泡排序、选择排序、插入排序、快速排序、归并排序等)、查找(线性查找、二分查找、哈希查找等)、图的遍历(深度优先搜索DFS和广度优先搜索BFS)、动态规划、贪心算法以及回溯法等。...
此外,数据结构和算法的学习不仅包括排序算法,还包括查找算法、图算法、树算法等多个方面,它们是计算机科学的基础,对于理解和解决复杂问题至关重要。学习这些知识能够帮助我们编写出更加高效、优化的代码,提高...
数据结构与算法是计算机科学的基础,对于任何编程学习者来说,理解和掌握它们至关重要。这个“数据结构与算法-----PPT版本”很可能包含了徐旭松教授或专家精心制作的一系列教学材料,旨在帮助学习者深入理解这些核心...
在数据结构与算法的学习过程中,快速排序算法是一种重要的排序算法,它具有排序速度快、就地排序的优点,但也具有不稳定性。以下是快速排序算法的详细实现报告。 快速排序算法的设计思想是,选择一个元素作为基准,...
在这个名为"数据结构与算法冒泡排序小程序"的项目中,我们专注于通过冒泡排序方法对输入的数组进行排序。 冒泡排序的工作原理是通过不断比较相邻元素并交换位置来逐步将最大(或最小)的元素“冒泡”到数组的一端。...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
在《数据结构算法与应用--C++语言描述》这本书中,作者深入浅出地介绍了各种基本和高级的数据结构及其对应的算法,并提供了详细的C++实现。以下是基于这个主题的详细知识点讲解: 1. **数组**:数组是最基础的数据...
本文档主要聚焦于初级水平的数据结构与算法的学习,适用于初学者掌握基础概念和技术要点。主要内容包括栈、队列、链表等基本数据结构以及递归的概念,并详细介绍了几种排序算法的实现方式。 #### 一、基本概念 **...
- 冒泡排序、选择排序和插入排序的基本思想及时间复杂度分析。 - 希尔排序(Shell Sort)的改进方法。 - 快速排序的分治策略及递归实现。 - **高级排序算法**: - 归并排序的合并策略及稳定性分析。 - 堆排序的...
在学习冒泡排序的基础上,可以进一步探讨优化策略,例如:设置标志位来判断某趟排序是否进行了交换,如果没有交换则说明序列已经有序,可以提前结束排序;或者设计双向冒泡排序,让最大值和最小值同时在一趟排序中...
- **排序算法**: 如冒泡排序、插入排序、快速排序等,这些算法的不同实现方式对于性能有着不同的影响。 - **查找算法**: 包括顺序查找、二分查找等,适用于不同类型的数据集。 - **递归与动态规划**: 这些高级算法...
常见的算法有排序(如冒泡排序、选择排序、插入排序、快速排序、归并排序)、搜索(如线性搜索、二分搜索)、图算法(如深度优先搜索DFS、广度优先搜索BFS、最短路径算法Dijkstra、Floyd-Warshall)等。理解和掌握...
以下是基于标题“数据结构与算法-java”及描述中提到的“数据结构与算法分析_Java语言描述高清版(第2版)1.pdf”所涵盖的一些关键知识点: 1. **数据结构**: - **数组**:最基础的数据结构,存储固定大小的同类型...
"数据结构--排序--思维导图" 数据结构中排序是指将一组无序的记录序列按照一定的规则排列成有序的序列,排序的目的是为了提高数据的存储和检索效率。排序算法的稳定性是指在排序过程中,如果待排序表中有两个元素Ri...
- **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,它们用于将一组数据按照特定顺序排列。 - **查找算法**:如线性查找、二分查找、哈希查找,用于在数据集中寻找特定元素。 - *...