话说这冒泡排序好久都没有用过了,忘得差不多了,但是由于目前的需要,只能再次重新学习了一下。
各种算法最好是用C/C++,因为执行效率高啊,在JAVA平台运行这些算法有些不适合,不过这个冒泡排序姑且用JAVA来测试一下。
下图是对它的各种复杂度的评价
最差时间复杂度
O(n2) |
最优时间复杂度
O(n) |
平均时间复杂度
O(n2) |
最差空间复杂度
O(n) total, O(1)auxiliary |
最佳算法
No |
性能分析:
若记录序列的初始状态为"正序",则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次交换,且不移动记录;反之,若记录序列的初始状态为"逆序",则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
下面是冒泡排序的执行过程:
冒泡排序算法的运作如下:
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
下面通过一个例子来查看这个算法每一轮知道最后的执行结果:
package test02;
import java.util.Arrays;
public class Test01 {
public static void main(String args[])
{
int[] a = {3,5,2,4,6};
sort(a, a.length);
System.out.println("最终结果=========================");
System.out.println(Arrays.toString(a));
}
public static void sort(int[] array,int size)
{
int i,j,temp;
for(i=0;i<size;i++)
{
for(j=0;j<size-i-1;j++)
{
if(array[j]>array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
System.out.println(Arrays.toString(array));
}
System.out.println("第"+i+"次----------------------");
}
}
}
运行结果如下:
[3, 5, 2, 4, 6]
[3, 2, 5, 4, 6]
[3, 2, 4, 5, 6]
[3, 2, 4, 5, 6]
第0次----------------------
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
第1次----------------------
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
第2次----------------------
[2, 3, 4, 5, 6]
第3次----------------------
第4次----------------------
最终结果=========================
[2, 3, 4, 5, 6]
对结果的分析:
第一轮:首先3和5比较,3不大于5,所以第一次比较不动,然后5和2比较,5大于2,所以交换5和2,变成
3,2,5,4,6,然后5和4比较,5>4,交换5和4,变成:3,2,4,5,6,5再和6比较,5小于6,所以不变。这就是第一轮的执行过程,也就是每一次都会沉下一个最大的数字
第二轮:由于沉下了最大的数字6,所以剩下了2,3,4,5。在这4个数字中再次执行上述的过程,知道最后
分享到:
相关推荐
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
详解Java常用排序算法-冒泡排序
基于python的排序算法-冒泡排序Bubble Sort
NULL 博文链接:https://xieyan30.iteye.com/blog/1922613
Bubble Sort-冒泡排序算法-少儿编程scratch项目源代码文件案例素材.zip
TIA博途_冒泡排序SCL算法_全局FC库文件_V15版本
经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - 堆排序Heap sort序 经典排序算法 - ...
冒泡排序
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
算法-数据结构和算法-9-冒泡排序.rar
java排序算法-大全.rar 集合了多种java排序算法
C#_基于C#实现的冒泡排序算法_Bubble-Sort
冒泡排序-排序过程 设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
Java后端算法-冒泡排序和选择排序对比
PHP_基于php实现的冒泡排序算法_BubbleSort
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...