| JavaScript, 冒泡排序, 算法

JavaScript中的冒泡排序

  1. 冒泡排序法想必大家都听说过吧，今天就给大家讲一讲关于冒泡排序法。
  2. 冒泡排序法的时间复杂度为O(n^2)，冒泡排序相对是比较简单的并且冒泡排序也是容易理解的一种排序算法，在面试中也是容易被考到的。
  3. 冒泡排序的一个基本思路是：

a. 从数组头部开始，不断比较相邻的两个元素的大小，让较大的元素逐渐往后移动（交换两个元素的值），直到数组的末尾。经过第一轮的比较，就可以找到最大的元素，并将它移动到最后一个位置。

b. 第一轮结束后，继续第二轮。仍然从数组头部开始比较，让较大的元素逐渐往后移动，直到数组的倒数第二个元素为止。经过第二轮的比较，就可以找到次大的元素，并将它放到倒数第二个位置。

c. 以此类推，进行 n-1（n 为数组长度）轮“冒泡”后，就可以将所有的元素都排列好。
总结：整个排序过程就好像气泡不断从水里冒出来，最大的先出来，次大的第二出来，最小的最后出来，所以将这种排序方式称为冒泡排序（Bubble Sort）。

下面给大家画一幅图大家就可以理解它的一个大致过程了：
冒泡排序解析图

在看了这幅过程图之后，我们就开始写js的代码了，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubble(arra){
        var temp;
        for(var i = 0 ; i < arra.length-1 ; i++){ //比较多少趟，从第一趟开始，从上图你就可以看到4个元素第一轮比较了3次，因此可以推断出为arra.length - 1次
            for(var j = 0 ; j< arra.length-i-1 ; j++){ //每一趟比较多少次数
                if(arra[j] > arra[j+1]){
                    temp = arra[j];
                    arra[j] = arra[j+1];
                    arra[j+1] = temp;
                }
            }
        };
    return arra;
    }
    var arrry = [7,2,5,3];
    var s = bubble(arrry);
    console.log(s);   // [2, 3, 5, 7]

如果对代码还有什么疑惑可以再看看上面我画的图，结合图再来看看代码会对你有一个更好的理解。