`

算法回顾之一:冒泡排序

 
阅读更多

数据结构与算法是计算机本科相关专业学生的必修课,我当年自然也是学过的,而且印象考试成绩还不错。

不过近期写了一个冒泡排序算法(不使用类库实现),竟然出现了Bug,实在惭愧。

仔细想想工作这几年一直都是使用Java集合框架和类库,因此感觉还是有必要再重温一下。

-----------------------------------------------------------

冒泡排序

基本原理:

依次比较相邻的2个元素,把小数放在前面,把大数放在后面。遍历数组的每一个元素后,最大的数放在了最后。

再次从头比较相邻2个元素,把小数放在前面,把大数放在后面。直到比较到倒数第二个数(倒数第一个数已经是最大的了)。

依此类推,直到将数组中所有元素都排序一遍。

程序实现:

 

public static void bubbleSort(){
	    int[] array=new int[]{9,8,7,6,5,4,3,2,1};
	    boolean noSwapFlag=true;//未发生交换标识
	    int temp=0;//临时变量,用于排序时的数据交换.
		for (int i=0;i<array.length-1;i++) {//数组中的已排序元素.
			noSwapFlag=true;//每轮排序前重置未交换标识
			for (int j=0;j<array.length-i-1;j++){//每一轮排序需要遍历的元素个数.
				//升序排序:如果前面的元素大于后面的元素,交换位置(小于为降序).
				if (array[j] > array[j+1]){
					temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
					//如果有交换时,未发生交换的标识置为false.
					noSwapFlag=false;
				}
			}
			System.out.println("Sort"+i+":"+Arrays.toString(array));
			if(noSwapFlag){//该轮排序中没有任何元素发生交换,代表已达到所需顺序.
				System.out.println("No swap!");
				break;
			}
		}
		System.out.println("Sort Result:"+Arrays.toString(array));
	}

 

性能分析:

1、如果目标序列为升序,而数组本身也是升序,那么只需要1次排序即可排出。排序次数为n-1次。

2、如果目标序列为升序,而数组全部元素逆序,那么需要n*(n-1)/2次比较和移动。

因此,冒泡排序的总时间复杂度为O(n^2).

 

空间复杂度:1。

稳定性:稳定的排序。

分享到:
评论

相关推荐

    冒泡排序详细教程学习攻略 冒泡排序知识点总结重点.docx

    三、冒泡排序的算法原理 四、冒泡排序的实现步骤 五、冒泡排序的优化策略 六、冒泡排序的复杂度分析 七、冒泡排序的实战应用 八、冒泡排序与其他排序算法的比较 九、总结与资源推荐 一、引言 重点内容: 引入排序...

    java 冒泡排序法 PPT文档

    冒泡排序是一种基础且经典的排序算法,主要应用于计算机科学领域,特别是在编程语言如Java中。它的名字来源于排序过程中较小的元素像气泡一样逐渐“浮”到数组或列表的顶端。这个PPT文档很可能是详细介绍了Java实现...

    奇偶冒泡排序的C语言实现

    奇偶冒泡排序是一种优化了传统冒泡排序算法的排序方法,主要目的是为了减少不必要的比较和交换操作,从而提高排序效率。在C语言中实现奇偶冒泡排序,我们需要理解其基本原理,并能够熟练地编写相应的代码。 首先,...

    冒泡排序c语言算法

    在开始讨论冒泡排序的具体实现之前,我们先简要回顾一下C语言的一些基础知识,这些基础知识对于理解冒泡排序的代码至关重要。 ##### 2.1 数据类型与变量 C语言支持多种数据类型,包括整型(int)、字符型(char)、...

    数据结构 与 基础算法,语雀导出的

    冒泡排序是一种简单的排序算法。其思想是通过不断地比较相邻的元素,大的元素将会被交换到右侧,最终使得整个数组有序。 快速排序 快速排序是一种高效的排序算法。其思想是通过选择一个基准元素,将数组分为两个...

    实验五:内部排序.docx

    - 交换排序:通过交换元素来排序,如快速排序、冒泡排序。 - 选择排序:每次选择最小(或最大)元素放入正确位置,如简单选择排序。 - 归并排序:分治法,将数据分成小块排序后再合并,时间复杂度为 O(n log n)。...

    数据结构排序实验报告

    - 学习并掌握多种排序算法(包括直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序等),同时理解它们的性能特点。 #### 实验环境配置 - **硬件需求**:一台装有Windows操作系统的计算机。 - **...

    用C语言编写冒泡排序

    冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 #### C语言基础...

    01-D-5 冒泡排序的分析1

    冒泡排序是一种基础的排序算法,其主要思想是通过重复遍历待排序的数列,依次比较相邻元素并根据需要交换它们的位置,使得较大的元素逐渐“浮”到数列的末尾,就像水底下的气泡逐渐上升到水面一样。在本节中,我们将...

    排序算法冒泡法教学设计.doc

    【排序算法】是计算机科学中一个基础且重要的概念,它涉及到如何有效地调整一系列数值或...在总结阶段,回顾关键知识点,提供相关学习资源,鼓励学生将所学应用于解决实际问题,进一步巩固和深化对冒泡排序算法的理解。

    数据结构排序算法python

    本资源包含了一个名为`SortSolution.py`的Python文件,里面实现了几种经典的排序算法,包括插入排序、选择排序、冒泡排序和快速排序。 1. **插入排序**: 插入排序是一种简单直观的排序算法,它的工作原理是通过...

    计算机微课教学设计.pdf

    - **知识总结**:回顾冒泡排序的原理、算法设计和相关拓展知识。 5. **教学特色**: - 整合碎片化资源,利用动画和代码执行来讲解抽象概念,提高教学效果。 - 通过实际数据的动态演示,使学生更易理解和掌握冒泡...

    算法:C语言实现(第5部分).

    - **常见算法分类**:排序算法(冒泡排序、快速排序等)、搜索算法(二分查找)、图算法(Dijkstra算法)等。 ### 三、C语言中的算法实现 #### 3.1 排序算法 排序算法是算法学习中最基础也是最重要的部分之一,在...

    用php实现几种常见的排序算法共6页.pdf.zip

    1. **冒泡排序**(Bubble Sort):这是一种简单的排序算法,通过重复遍历待排序序列,比较相邻元素并交换顺序来完成排序。在PHP中,你可以创建一个循环,嵌套另一个循环来实现这个过程。 2. **选择排序**...

    聆听排序算法的声音

    首先,我们来回顾一下经典的冒泡排序(Bubble Sort),这也是压缩包中文件名“bubble_8_elements.mid”所对应的排序算法。冒泡排序是一种简单的比较排序,它的基本思想是通过重复遍历待排序的元素列表,依次比较相邻...

    冒泡法与选择法排序效率比较.doc

    冒泡排序和选择排序是两种常见的简单排序算法,它们都在计算机科学中被广泛用来组织数据。这两种方法的主要区别在于它们如何找到并交换未排序元素的位置。 冒泡排序的工作原理是通过重复遍历待排序的列表,比较相邻...

    45个经典的算法Flash动画演示

    1. **排序算法**:包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。这些是基础的算法,用于对数据进行有效排列,理解它们的工作原理有助于优化时间复杂度。 2. **查找算法**:如线性查找、二分查找。线性...

Global site tag (gtag.js) - Google Analytics