算法学习之冒泡排序

算法在编程中的重要性开篇就不赘述啦，我们直接步入正题，开启算法学习之旅。
首先开始排序算法的学习，这也是面试比较常问的。今天我们就先来看一下冒泡排序。冒泡排序的思想是每轮都让 相邻的两个元素进行比较 ，如果前一个元素大于后一个元素则交换位置，这样下来 每一轮 比较完成之后就会将最大的那个元素放在数组的最右边。
比如我们以数组

[5, 3, 7, 2, 9, 6, 8, 1, 0, 4]

为例，第一轮是

1. 从 5 开始，并和与他相邻的元素进行比较，发现 3 小于 5，那么我们交换他两的位置，
2. 然后接着拿 5 和 7 进行比较，发现 5 小于 7，则继续
3. 将 7 和他的下一个元素进行比较，若 7 大于下一个元素则进行 1 步骤，否则进行 2 步骤。直至比较到数组的最后一个元素。

第二轮就是重复第一轮的操作，直至比较到数组的倒数第二个元素。
……
……
……
理解了思想我们来看下代码实现。

var arr = [5, 3, 7, 2, 9, 6, 8, 1, 0, 4];
for(var i = 0, len = arr.length - 1; i < len; i++){for(var j = 0, lenj = arr.length - 1 - i; j < lenj; j++){if(arr[j] > arr[j+1]){var temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    } 
} 

这样下来冒泡排序的时间复杂度为 O(N^2)，我们在优化一下这段代码，比如在第 k 轮的时候没有进行元素交换，那么是不是就说明在第 k 轮时该数组就已经是一个有序数组轮呢？答案是肯定的，那么我们对上述代码做如下修改：

var arr = [5, 3, 7, 2, 9, 6, 8, 1, 0, 4],
    flag = false;
for(var i = 0, len = arr.length - 1; i < len; i++){
    flag = true;
    for(var j = 0, lenj = arr.length - 1 - i; j < lenj; j++){if(arr[j] > arr[j+1]){
            flag = false;
            var temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
    if(flag) break;
} 

我们定义了一个 flag 标志，当数组在某一轮没有进行任何元素交换的时候，我们就可以知道此时的数组已经是一个有序数组，因此就结束循环。
对冒泡排序还有更多的可扩展性，欢迎各路大神指点。