气泡排序的经典算法(简略版)
冒泡排序
算法概念
了解一个知识,必须先要从其含义开始。 冒泡排序,什么是冒泡排序,这种排序方法是通过相邻的两个元素两两比较,根据大小来交换位置,最值元素就像气泡一样从左侧向右侧移动,故名冒泡排序。冒泡排序是一种计算机科学领域的较简单基础的排序算法。其基本思路是,对于一组要排序的元素列,依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面,如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成。
举一个例子说明冒泡排序是如何排序的:水桶位置例子
现有4个水桶【A、B、C、D】,每个水桶质量各不同,现要球按照质量大小,从小到大排序。(其中大小关系为【B>D>A>C】)
现如今按照冒泡排序的排序方式进行排序。首先比较A和B的大小关系,A小于B,那么AB不需要交换位置。则继续进行B和C的比较,由B和C大小关系比较,B大于C那么,B和C交换位置,此时位置顺序为【A、C、B、D】。在由B和D,B大于D,则B和D交换位置。此时位置顺序为【A、C、D、B】。 然后进行第二轮的排序 A与C进行比较,A>C,交换A与C之间的位置,则此时的位置顺序为【C、A、D、B】。再比较A与D的关系,A小于D,则不需要交换,此时的位置顺序为【C、A、D、B】此时排序完毕,不需要再一次重复性的比较。
算法图例
第一轮比较
第二轮比较
经过两轮比较就将水桶的排序位置搞定
代码实现
采用JS来实现冒泡排序代码
定义一个数组
var arr=[6,10,12,23,43,52,58,68,70,94,128]
冒泡方法实现
for(var i=0;i<arr.length;i++){
for(var j=1;j<arr.length-i;j++){
if(arr[j-1]>arr[j]){
var temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
Java实现
int [] arr = new int[]{34,5,-5,9,86,26};
for(int i = 0;i < arr.length - 1;i++){
for(int j = 0;j < arr.length - 1 -j;j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
代码解析
外部循环,遍历循环的总次数
for(var i=0;i<arr.length;i++){
//方法体
}
内部for循环
for(var j=1;j<arr.length-i;j++){
//方法体
}
循环匹配次数,每次匹配后减少一次循环,因为最后一个数组都是已经循环完成的,不需要重复进行。
交换代码
if(arr[j-1]>arr[j]){
var temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
当元素i-1的元素大于i元素位置时,则说明不符合排序升序,需要交换元素位置。
总结
冒泡排序是经典算法中的较为简单的排序算法之一,运用较为广泛,经典之经典,推敲算法。跟着敲一遍,更有利于算法的学习。
更详细的冒泡排序请详见主页顶置的冒泡排序文章。
上一篇: 冒牌排序法详解
推荐阅读
-
Java 中的经典算法冒泡排序(Bubble Sort)
-
气泡排序(超级详细)--升序",从小到大;另一种是 "降序",从大到小。该主题可抽象为 "按升序对 n 个数字排序 "的一般形式。 排序是一种重要的基本算法。排序的方法有很多种,但在本题中我们将使用冒泡排序法。 冒泡法的基本思想 冒泡法的基本思想是,每次比较相邻的两个数字时,较小的那个会被移到前面。如果有 5 个数字9,8,5,2,0,第一次将前两个数字 8 和 9 互换。第二次将第二个和第三个数字(9 和 5)对调......这样一共对调 4 次,得到 8-5-2-0-9 的顺序,可以看到:最大的数字 9 一直在 "下沉",成为最下面的一个数字,而小的数字 "上升" 最小的数字 "上升"。最小的数字 0 已经向上 "浮 "了一个位置。经过第一次比较(共 4 次比较和交换),得到了最大的数字 9。 然后进行第二趟比较,对剩下的前 4 个数字(8、5、2、0)进行新一轮比较,这样第二个最大的数字就 "沉到了底部"。同样,按照上述方法进行第二轮比较。经过 3 次比较和交换,我们得到了第二大数 8。 按照这个规律,我们可以推断出,比较 5 个数字需要 4 次旅行,才能将 5 个数字从小到大排列起来。在第一次旅行中,两个数字之间进行了 4 次比较,在第二次旅行中,进行了 3 次比较......在第四次旅行中,只进行了一次比较。 思路总结 总结:如果有 n 个数字,那么要进行 n-1 次比较。在第一次行程中进行 n-1 次比较,在第 i 次行程中进行 n-i 次比较。
-
C 语言版冒泡排序算法详解 - 三、C 程序的冒泡排序算法
-
[排序算法] - 气泡排序的三种实现(Java)
-
经典排序算法 (1) - 气泡排序算法详情
-
排序算法 (I) - 用气泡法进行排序的算法
-
气泡排序的经典算法(简略版)
-
气泡排序算法的详细分析
-
经典排序算法 - 气泡排序
-
排序算法]史上最简单易懂的 [气泡排序]。