数据结构与算法是计算机本科相关专业学生的必修课,我当年自然也是学过的,而且印象考试成绩还不错。
不过近期写了一个冒泡排序算法(不使用类库实现),竟然出现了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。
稳定性:稳定的排序。
分享到:
相关推荐
三、冒泡排序的算法原理 四、冒泡排序的实现步骤 五、冒泡排序的优化策略 六、冒泡排序的复杂度分析 七、冒泡排序的实战应用 八、冒泡排序与其他排序算法的比较 九、总结与资源推荐 一、引言 重点内容: 引入排序...
冒泡排序是一种基础且经典的排序算法,主要应用于计算机科学领域,特别是在编程语言如Java中。它的名字来源于排序过程中较小的元素像气泡一样逐渐“浮”到数组或列表的顶端。这个PPT文档很可能是详细介绍了Java实现...
奇偶冒泡排序是一种优化了传统冒泡排序算法的排序方法,主要目的是为了减少不必要的比较和交换操作,从而提高排序效率。在C语言中实现奇偶冒泡排序,我们需要理解其基本原理,并能够熟练地编写相应的代码。 首先,...
在开始讨论冒泡排序的具体实现之前,我们先简要回顾一下C语言的一些基础知识,这些基础知识对于理解冒泡排序的代码至关重要。 ##### 2.1 数据类型与变量 C语言支持多种数据类型,包括整型(int)、字符型(char)、...
冒泡排序是一种简单的排序算法。其思想是通过不断地比较相邻的元素,大的元素将会被交换到右侧,最终使得整个数组有序。 快速排序 快速排序是一种高效的排序算法。其思想是通过选择一个基准元素,将数组分为两个...
- 交换排序:通过交换元素来排序,如快速排序、冒泡排序。 - 选择排序:每次选择最小(或最大)元素放入正确位置,如简单选择排序。 - 归并排序:分治法,将数据分成小块排序后再合并,时间复杂度为 O(n log n)。...
- 学习并掌握多种排序算法(包括直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序等),同时理解它们的性能特点。 #### 实验环境配置 - **硬件需求**:一台装有Windows操作系统的计算机。 - **...
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 #### C语言基础...
冒泡排序是一种基础的排序算法,其主要思想是通过重复遍历待排序的数列,依次比较相邻元素并根据需要交换它们的位置,使得较大的元素逐渐“浮”到数列的末尾,就像水底下的气泡逐渐上升到水面一样。在本节中,我们将...
【排序算法】是计算机科学中一个基础且重要的概念,它涉及到如何有效地调整一系列数值或...在总结阶段,回顾关键知识点,提供相关学习资源,鼓励学生将所学应用于解决实际问题,进一步巩固和深化对冒泡排序算法的理解。
本资源包含了一个名为`SortSolution.py`的Python文件,里面实现了几种经典的排序算法,包括插入排序、选择排序、冒泡排序和快速排序。 1. **插入排序**: 插入排序是一种简单直观的排序算法,它的工作原理是通过...
- **知识总结**:回顾冒泡排序的原理、算法设计和相关拓展知识。 5. **教学特色**: - 整合碎片化资源,利用动画和代码执行来讲解抽象概念,提高教学效果。 - 通过实际数据的动态演示,使学生更易理解和掌握冒泡...
- **常见算法分类**:排序算法(冒泡排序、快速排序等)、搜索算法(二分查找)、图算法(Dijkstra算法)等。 ### 三、C语言中的算法实现 #### 3.1 排序算法 排序算法是算法学习中最基础也是最重要的部分之一,在...
1. **冒泡排序**(Bubble Sort):这是一种简单的排序算法,通过重复遍历待排序序列,比较相邻元素并交换顺序来完成排序。在PHP中,你可以创建一个循环,嵌套另一个循环来实现这个过程。 2. **选择排序**...
首先,我们来回顾一下经典的冒泡排序(Bubble Sort),这也是压缩包中文件名“bubble_8_elements.mid”所对应的排序算法。冒泡排序是一种简单的比较排序,它的基本思想是通过重复遍历待排序的元素列表,依次比较相邻...
冒泡排序和选择排序是两种常见的简单排序算法,它们都在计算机科学中被广泛用来组织数据。这两种方法的主要区别在于它们如何找到并交换未排序元素的位置。 冒泡排序的工作原理是通过重复遍历待排序的列表,比较相邻...
1. **排序算法**:包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。这些是基础的算法,用于对数据进行有效排列,理解它们的工作原理有助于优化时间复杂度。 2. **查找算法**:如线性查找、二分查找。线性...