Fork me on GitHub

排序算法-冒泡排序

algorithm/bubble_sort/banner

前端也来学习算法之冒泡排序算法冒泡排序算法它是最慢的排序算法之一,但是也是一种最容易实现的排序算法~

介绍

之所以叫冒泡排序是因为使用这种排序算法排序时,数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列,较大的值会浮动到数组的右侧,而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动,比较相邻的数据,当左侧值大于右侧值的时候将它们进行互换。

比如下面的简单列表例子。

E A D B H

经过第一次的排序后,列表会变成:

A E D B H

前面两个元素进行了交互。接下来再次排序:

A D E B H

第二个元素和第三个元素进行了交互。继续进行排序:

A D B E H

第三个元素和第四个元素进行了交换。这一轮最后进行排序:

A D B E H

因为第四个元素比最后一个元素小,所以比较后保持所在位置。反复对第一个元素执行上面的操作(已经固定的值不参与排序,如第一轮固定的H不参与第二轮的比较了),得到的最终结果如下:

A B D E H

上面的数据还是比较少,而且是文字描述,不够直观,看下下面的gif图,或许你能够更好理解了。

algorithm/bubble_sort/bubble_sort_demo

你可以直接进入旧金山大学的David Galles教授做的站点–用HTML5实现的各种排序算法的动画比较进行查看更加详细的演示。

代码实现

上面已经讲了冒泡排序的原理了,接下来我们来用代码实现一下:

1
2
3
4
5
6
7
8
9
10
11
// 冒泡排序
function bubbleSort(arr){
var numElements = arr.length;
for(var outer = numElements-1 ; outer >= 1; outer--){
for(var inner = 0; inner <= outer-1 ; inner++){
if(arr[inner] > arr[inner+1]){
swap(arr , inner , inner+1);
}
}
}
}

上面只是给出了冒泡排序的核心代码,这里贴太多出来很是具有拉长篇幅的嫌疑。所以,详细代码请前往我的仓库demos/algorithm/bubble_sort.js

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)