js算法初窥01（排序算法01-冒泡、选择、插入）

function ArrayList() {
    var array = [];

    this.insert = function (item) {
        array.push(item);
    };

    this.toString = function() {
        return array.join();
    };
}

//交换数组中两个相邻元素的方法，传入的是相关的数组，以及相邻两个元素的下标。
var swap = function (array,index1,index2) {
    // 这里，是最“普通”的方式，通过一个中间量来存储index1元素，因为要把index1的值设置为index2，然后再把index2的值设置为刚才存储index1的aux变量。
    // 希望我上面说的足够清楚。
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
    // 但是我们可以有更为简便的方式来做到替换两个数组元素位置的方式。
    // 一个是下面的ES6新增的方法。数组的解构赋值。不多说，大家可以自行去查看。
    //[array[index1],array[index2]] = [array[index2],array[index1]];
    // 另外一个方法是利用数组的splice方法，删除从index1开始的两个元素，并且在删除的位置插入index2，和index1以达到替换元素的目的。
　　// 如果你对数组方法还不是很清楚，请看这里用js来实现那些数据结构02（数组篇02-数组方法）
　　//array.splice(index1,2,array[index2],array[index1]);
};
　　// 这是最简单，当然也是最慢的排序方法，我们需要两层循环来判断值得大小，以此来一步一步确定每一个值得位置。
　　// 这里我要刨根问底一下，为什么外层循环（i）循环的是数组元素的长度，而内层（j）是比数组长度少1的循环次数？
　　// 因为这是可以保证每两个元素都进行过比较的最小的循环次数，不信你把两次循环的次数增加（length +100000）;来试一下，发现结果仍旧是我们想要的。（当然，这更耗费时间。）
　　// 但是你把次数减得更少就不行了，排序的结果就不对了（其实这里可以合理的减少内层循环的次数，后面说）。你还可以这么理解，外层循环控制我们有多少个数需要比较，内层循环去具体的操作两个数的比较。
 this.bubbleSort = function () {
     var length = array.length;
     for(var i = 0; i < length; i++) { //i=0,1,2,3,4...length-1;
         //console.log(i,"i");
         for(var j = 0; j < length-1;j++) {//j = 0,1,2,3,4...length - 1 - 1;
             //console.log(j,"j");
             if(array[j] > array[j+1]){
                 swap(array,j,j+1)
             }
         }
     }
 };


//我们来写一个简单的方法生成一个未排序的arraylist。//这个方法是在构造函数外的。你不用也可以。只是为了方便生成一个数组罢了。
function creatArrayList (size) {
    var array = new ArrayList();
    for(var i = size; i > 0; i--) {
        array.insert(i);
    }

    return array;
}

var arraylist = creatArrayList(5);
console.log(arraylist.toString());//5,4,3,2,1
arraylist.bubbleSort();
console.log(arraylist.toString());//1,2,3,4,5

　　 //咱们看看modifiedBubbleSort和bubbleSort的区别，唯一不同的地方就在于内层循环的时候在for循环的第二个条件中多减了一个i。这么做的用意是什么呢？
    // 我们一点一点来捋一下这点点代码。假设我们的数组是【5，4，3，2，1】；当i = 0的时候(第一次外循环)，我们拿5去依次和4，3，2，1来比较，最后数组渐变成了【4，3，2，1，5】;
    // 那么此时，5就是最大的，当i=1的时候(第二次外循环)。此时我们的内循环就不再需要去拿当前的j去与5（也就是数组中确定了的最大的）比较。
    // 外层每循环一次，内层中的每个元素就相互交换了一下位置（如果符合条件的话），最终每一次内层循环完毕，都会确定一个当前轮数最大的值。
    // 那么既然我们已经知道最大的值是什么，就无需在后面的循环轮数中再去和已经确定了位置的值去做比较了。这样就可以提高一点我们的执行效率。
    // 这里再多句嘴，当i = 0时，j = 0，j < length - 1 - 0;当i = 1时，j = 0，j < length - 1 - 1;(要理解这句话)
    this.modifiedBubbleSort = function () {
        var length = array.length;
        for(var i = 0; i < length; i++) {
            for(var j = 0; j < length - 1 - i;j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    };

//其实选择排序也并不复杂，我们来一起看一看。
this.selectionSort = function () {
    //首先，我们声明一个存储数组长度的变量，以及一个存储当前最小值的变量，哦不对，存储当前最小值的对应下标的变量。
    var length = array.length,indexMin;
    // 在外层循环，我们循环次数是整个数组的长度。
    for(var i = 0; i < length - 1; i++) {
        // 这里，最开始的循环我们也不知道谁是最小的，所以我们就把第一个值得下标作为最小值得下标。
        indexMin = i;
        // 内层循环，我们会依次比较当前最小值（也就是indexMin对应的值）和数组中的其它值。
        // 这里，为什么是j=i呢？
        // 我们每一次外层循环，都会确定一个最小值并把最小值放置在相应的位置（从下标0开始每次外循环都会往后加1）。
        // 那么我们就不需要再去比较开始循环过比较过的下标了，所以我们每次外层循环过后，内层循环都从i的位置开始就可以了。
        // 有点类似于modifiedBubbleSort的j<length - 1 - i;
        for(var j = i; j < length; j++) {
            // 这样，我们就可以判断出最小值是什么，如果indexMin所对应的值比j所对应的值还要大，说明最小值对应的下标应该为j。
            if(array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        // 在外层循环一次结束后，如果i（最开始我们确定的最小值）不等于indexMin。这说明i并不是最小值。我们就交换两个值的位置。
        // 如果相等，说明当前的indexMin就是最小值，无需交换位置。
        console.log(i,indexMin)
        if(i !== indexMin) {
            swap(array,i,indexMin)
        }
    }
};

this.insertionSort = function () {
    //j和temp分别用来存储当前的下标和当前下标所对应的值。
    var length = array.length,j,temp;
    // 为什么i要从1开始呢？因为index为0的元素我们视为已经排序过的了。

    for(var i = 1; i < length; i++) {
        // 我们用j来存储当前要比较的值的下标也就是i，因为0上的元素已经排序过了（我们默认这样做的）。
        j = i;
        // 同样，我们要比较当前索引的值得大小来确定是否需要换位，所以我们还要有一个临时存储当前下标所对应的值的变量。
        temp = array[i];
        // 如果j>0说明是数组中的元素，
        // 并且，如果当前j(i)的前一个元素（j-1）比当前的变量大，那么就把j(i)的值设置为j-1的值，也就是把j(i)的位置往后挪了一个。
        // 直到array[j - 1] > temp为false为止。为什么不说j>0这个条件呢？因为这是保证数组正确对比的一个防护层，当然，它是很重要的。
        // 这里有一个十分必要且需要注意的point，就是我们的变量j的值的问题。
        // 我们在循环直到条件不成立跳出循环的时候，此时的j就是需要把临时存储array[i]的值（也就是temp）插入的地方。
        // 因为，我们在while循环中，每次循环都会用j--来使下标的位置一点点往前移动，直到条件不成立后，我们得到了一个应该插入temp的位置的j。
        while (j > 0 && array[j - 1] > temp) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
};