计算机是一种很傻的工具，傻到几乎没有智商，它可以连续几年做同一件事情而毫无怨言，但是如果你不告诉他怎么做，他什么事情也不会做。你告诉计算机你要怎么做，计算机会“固执”，坚决的执行你的指令，不会有任何改变，哪怕浪费资源。很多时候，我写程序的时候太片面，不能够考虑较优的效率，只是单纯的实现功能或效果。例如：冒泡排序算法。

冒泡排序算法的原理 随处可以搜得到看的见，即：将被排序的记录数组A[1...N] 垂直排列，每一个记录A[i]看作重量为R[i].key的气泡.根据轻气泡不能在重气泡之下的原则,从下往上扫描数组A.凡扫描到违反本原则的轻气泡，就让他往上漂浮, 如此反复进行。知道较后任何两个气泡都是轻者在上，重者在下为止为止。

function popsort()  
{  
    var i = 0;  
    var j = 0;
    var tmp = 0;  
    for (i  = 0; i < n - 1; i++)  
    {  
        for (j = 0; j < n - i - 1; j++)  
        {  
            if (a[j] > a[j + 1])  
            {  
                tmp = a[j];  
                a[j] = a[j + 1];  
                a[j + 1] = tmp;  
            }  
        }  
    }  
} 

上图为冒泡排序过程，这里考虑升序状态。冒泡排序的思想就是首先将较大的数据换到数组的末端（假设数组长度长位N）。如果a[j+1]

它的时间复杂度非常容易理解:O(N^2). 但是我们仔细看看上面的图.从第六次循环的时候整个数组其实已经排好序了，后面的循环其实都是多余的操作。我们可不可以这么想. 如果我循环一趟没有发生交换，那么这个数组整个就排好序了.这里认真想，如果你一趟下来下来没有交换任何数据，说明你这个数组每一个位置a[i]

function popsort() {
var i = 0; 
var j = 0;
var tmp = 0; 
var pos = 1；
for (i = 0; i < n - 1; i++) 
{ 
if(pos == 0)
break；
pos = 0；
for (j = 0; j < n - i - 1; j++) 
{ 
if (a[j] > a[j + 1]) 
{ tmp = a[j]; 
a[j] = a[j + 1];
 a[j + 1] = tmp; 
}
}
} 
}

运行结果我们看到了程序减少了循环次数，节约了效率,现在程序较好的时间复杂度为O(N). 就是刚刚好数组有序的时候.较坏的时间复杂度还是O(N^2)。

是否还能优化呢？

假设每次较后交换的地方为k. 那么a[k]~a[N]一定是有序的。

function popsort()  
{  
    var i = 0;  
    var j = 0;  
    var tmp = 0;  
    var Pos = 1;  
    var K = n-1;  
    var M = 0;  
  
    for (i = 0; i < n - 1; i++)  
    {  
        if (Pos == 0)  
            break;  
  
        Pos = 0;  
  
        for (j = 0; j < K; j++)  
        {  
            if (a[j] > a[j + 1])  
            {  
                Pos = 1;  
                tmp = a[j];  
                a[j] = a[j + 1];  
                a[j + 1] = tmp;  
                M = j;  
            }  
        }  
        K = M;  
    }  
}