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

今天重温算法，一开始没看明白冒泡排序和选择排序的区别，因为他们排序过程中都是通过相邻的数据比较找到最小/最大的数据，看了实现代码才明白，冒泡排序在比较的过程中待排序的数据会发生位置改变，而选择排序法在比较过程中，是记录较大/较小数据的索引，只有在找到最大/最小数据的时候才会发生交换。

冒泡排序

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现

Array.prototype.bubble_sort = function() {
    var i, j, temp;
    for (i = 0; i < this.length - 1; i++)
        for (j = 0; j < this.length - 1 - i; j++)
            if (this[j] > this[j + 1]) {
                temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
    return this;
}

选择排序

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

参考资料:
https://zh.wikipedia.org/wiki/冒泡排序
https://zh.wikipedia.org/wiki/选择排序
https://www.runoob.com/w3cnote/selection-sort.html