传统的三种排序以及冒泡排序的优化算法

　　因为这三种基本的排序算法原理都很简单，所以在思路这块我就不做过多的解释了，我们把重点放在最后的冒泡排序如何优化上面

　一、选择排序

　二、快速排序

    三、冒泡排序

　　通过上面的代码可以看出来，通过两次简单的for循环，并且不加任何判断语句的形式的算法注定是低效的，以下是对冒泡排序算法的三种优化

---

 （1）、当我们对一个数组arr=[9,1,2,3,4,5,6]进行排序的时候，我们正常冒泡排序的话，还是会每个数字都排一次，但事实上我们第一次排序进行完之后，数组就已经变成[1,2,3,4,5,6,9]，已经达到我们想要的效果了，所以已经不需要再进行其他元素的排序了，所以我们要对这种传统的冒泡排序算法做一个优化，思路大概是这样的：我们定义一个flag，当某一次排序中没有发生元素的交换的话，设置flag为false，当flag为false的时候直接结束后面的循环，这样的话数组就不会再进行后面的无意义的排序了，代码实现：

    var arr = [9,1,2,3,4,5,6]
    function bubbleSort(arr){
    var temp;
    var flag;       //定义flag，用来判断数组是否已经有序
    for(var i=0;i<arr.length;i++){
        flag = true     //我们设置flag初始值为true
        for(var j=0;j<arr.length-i;j++){
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = false;   //我们自己规定flag为false的时候说明数组需要继续排序
            }
        }
        if(flag){   //我们可以规定如果某次循环后flag依然为true的话，表明这次没有进行重新的元素交换，也就是说没有进行重新排序，那么此时数组中元素已经有序了，所以我们可以直接break跳出循环，return出数组
            break;
        }
    }

    return arr;
}

（2）、第二种优化是从另一个角度来考虑的，并且也是基于第一次优化的思想，我们每次排序后，数组的后面有一部分已经有序了，所以我们也不需要再和后面已经排好序的元素再进行比较了，我们可以这样做，用一个变量来记录下最后一次发生交换的位置，后面没有发生交换的其实已经有序了，所以可以用这个值来作为一一次我们比较结束时的位置，将会减少很多次没必要的排序过程，代码实现如下：

    var arr = [9,1,10,5,6,3,0]
    function bubbleSort(arr){
    var temp;
    var flag;       //定义flag，用来判断数组是否已经有序
    var lastindex = 0;       //定义lastindex，用来判记录每次排好序时的最后一次交换的位置
    var k = arr.length-1;          //用来和lastindex配合，作为每次循环的边界值，实现不会进行没必要排序的效果
    for(var i=0;i<arr.length;i++){
        flag = true     //我们设置flag初始值为true
        for(var j=0;j<k;j++){
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                flag = false;   //我们自己规定flag为false的时候说明数组需要继续排序
                lastindex = j;  //来记录最后一次交换元素的下标
            }
        }
        k = lastindex
        if(flag){   //我们可以规定如果某次循环后flag依然为true的话，表明这次没有进行重新的元素交换，也就是说没有进行重新排序，那么此时数组中元素已经有序了，所以我们可以直接break跳出循环，return出数组
            break;
        }
    }

    return arr;
}