`
zy19982004
  • 浏览: 652946 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
博客专栏
F6f66edc-1c1a-3859-b76b-a22e740b7aa7
Hadoop学习
浏览量:249395
社区版块
存档分类
最新评论

数据结构与算法学习一:冒泡排序

阅读更多

一.排序方法

  1. 将被排列的数组data[0...n]垂直排列,每个元素data[i]看作是一个气泡,气泡的重量就是data[i]的值。
  2. 从最下面一个气泡data[n]开始扫描,比较其与上一个气泡data[n-1]的重量,data[n] < data[n-1]则交换;然后比较data[n-1]与data[n-1-1]...一轮下来,最轻的气泡跑到了最上面data[0]的位置。
  3. 重复2过程,让第二轻的气泡跑到data[1]的位置;再次重复...

 

二.动画演示

      http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/maopaopaixu.htm

 

 

三.Java代码

 

	public static int[] bubbleSort(int[] data) {
		int temp = 0;
		for(int i=0; i < data.length -1; i++) { //每一轮
			boolean exchange = false;			//每一轮设置一个是否有元素交换的标志
			int j = data.length -1;
			for(; j > i; j--) {
				if(data[j] < data[j-1]) {     	//元素和上一个元素比较
					temp = data[j];
					data[j] = data[j-1];
					data[j-1] = temp;
					exchange = true;        	//有元素交换
				}
			}
			if(!exchange) {      				//如果一轮下来,没有元素交换,说明data已经是排好序了,无需进行下一轮
				break;
			}
		}
		return data;
	}

 

 

四.时间复杂度和稳定性

  1.  最好时间复杂度
    1. 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值。
    2. Cmin=n-1=O(n)
    3. Mmin=0
    4. 冒泡排序最好的时间复杂度为O(n)
  2. 最坏时间复杂度
    1. 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值。
    2. Cmax=n(n-1)/2=O(n2)
    3. Mmax=3n(n-1)/2=O(n2)
    4. 冒泡排序的最坏时间复杂度为O(n2)
  3. 平均时间复杂度
    1. O(n2)
  4. 冒泡排序是就地排序,且它是稳定的。

五.算法优化

  1. 设置exchange标志。如果不设置,Cmin=n(n-1)/2=O(n2)
1
1
分享到:
评论
1 楼 这些年 2014-06-03  
讲的不错,哪个动画杠杠的

相关推荐

    数据结构与算法之冒泡排序pta:基于C语言的编程实践与测试

    本资源适合数据结构与算法学习者和考生使用,帮助他们通过项目实践来加深对冒泡排序算法的理解和掌握,提高编程的能力和水平。 提供了多种算法演示和验证的功能,如输入和输出待排序的数据,显示冒泡排序的过程和...

    排序算法 数据结构 冒泡排序

    数据结构排序算法中的冒泡排序,是我们学院学习计算机语言室接触到的第一个算法,可以说是最基础的一个排序算法

    数据结构经典排序算法之比较

    排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡...在研究学习了之前几种排序算法的基础上,讨论发现一种新的排序算法,并通过了进一步的探索,找到了新的排序算法较之前几种算法的优势与不足。

    Java数据结构与算法学习笔记之排序

    Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.

    数据结构与算法综合资料库

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    java数据结构与算法学习.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    #数据结构与算法java实现 #包括排序,线性表,树,图,散列等基础数据结构.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法综合资料库.CHM

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    Data Structures and Algorithms 数据结构与算法学习笔记.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法学习.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    《数据结构与算法:Java语言描述》源码.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构及算法学习.zip

    算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构和算法学习.zip

    算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    Java数据结构和算法学习.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法复习(Java):排序、字符串、数组、链表、二分查找、二叉树.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    【尚硅谷】数据结构与算法(Java数据结构与算法).zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    《数据结构与算法分析》书中数据结构与算法实现.zip

    算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法学习总结.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法学习笔记.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

    数据结构与算法学习~.zip

    逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。

Global site tag (gtag.js) - Google Analytics