冒泡排序和选择排序

关于数组的操作，经常会涉及到时间复杂度，空间复杂度，稳定性和不稳定性几个概念。

时间复杂度：一个程序执行所需要的时间，主要针对的是for循环

空间复杂度：程序所需的存储空间，可以估算出内存的大概使用情况

稳定性：如果a = b，a在b的前面，排序后a任然在b的前面

不稳定性：如果a = b，a在b的前面，排序后a在b的后面

具体的归纳情况可以见下图：

数组的排序方法

冒泡排序法

原理：
依次比较数组里面每相邻的两个元素。如果前面的数比后面的数大，则将两个数交换顺序。也就是找到数组的最大数放在最后一位。

重复相同的规律，每次找出剩下数组里面的最大数放在最后面，直到数组有序排列为止。

具体实现(原型链编程)：

Array.prototype.bubbleSort = function () {
    var temple;
    for (var i = 0; i < this.length - 1; i++) {     //this指向被调用的对象
        for (var j = 0; j < this.length - 1 - i; j++) {
            if (this[j] > this[j+1]) {
                temple = this[j];
                this[j] = this[j+1];
                this[j+1] = temple;
            }
        }
    }
    return this;
}

var arr = [1, 5, 2, 7, 13, 2, 3, 4, 34];
var arrSort = arr.bubbleSort();     //方法调用
console.log(arrSort);   //[1, 2, 2, 3, 4, 5, 7, 13, 34]

需要注意的是，每两个数进行比较大小时，知道第n - 1个数，则可以比较出第n - 1个数和第n个数的大小。所以第一个for循环终止条件为arr.length - 1。

第二个for循环时，当i = 0时，需要循环的次数为arr.length - 1,第一次循环结束的结果是选出最大的数放在数组最后，即排序后的数组为[1, 2, 5, 7, 2, 3, 4, 13, 34]。

当i = 1时，循环次数为arr.length - 1 - 1，即最后一个数已经确定大小，不需要比较。还有余下数组的最后一位也不需要比较。

当然啦，这样做是为了节省时间复杂度，当两圈for循环的终止条件改为arr.length也是可以的。

选择排序

原理：
选择排序是指选出数组里面的第一个数依次和后面的每个数作比较，如果后面的数比第一个数小，交换顺序（选出最小的数放在第一位）。

再选出第二个数依次和后面的每个数作比较，选出余下数组里面最小的放在第二位。

重复以上规律，知道数组有序为止。

具体实现：

Array.prototype.selectSort = function () {
    for (var i = 0; i < this.length - 1; i++) {     //this指向被调用的对象
        for (var j = i + 1; j < this.length; j++) {
            if (this[i] > this[j]) {
                temple = this[i];
                this[i] = this[j];
                this[j] = temple;
            }
        }
    }
    return this;
}

var arr = [1, 5, 2, 7, 13, 2, 3, 4, 34];
var arrSelect = arr.selectSort();   //方法调用
console.log(arrSelect);    //[1, 2, 2, 3, 4, 5, 7, 13, 34]

冒泡排序和选择排序的区别

比较冒泡排序和选择排序，发现他们其实实现原理都是一样的。

区别在于，冒泡排序是每两个相邻元素作比较，每次排序的结果是选出当前数组中的最大元素放在数组最后。
选择排序是第一个元素依次和后面的每个元素比，选出最小的元素放在数组第一位。依次重复类推。

冒泡排序是先确定最大元素放在最后，选择排序先确定最小元素放在第一位，所以他们最终的结果都是数组里面的数升序排列。