冒泡排序

冒泡排序是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

算法步骤

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

动图演示

Untitled

———— 动图来自《菜鸟教程》

说明：绿色表示当前正在比较的两个相邻元素；橘黄色表示已排完序的元素，不再参与后续的比较

代码实现

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 相邻两两比较，每轮过后从后往前确定一个排好序数字，所以外层for(len-1)，内层(len - i - 1)
function myBubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) { // 趟数
        for (var j = 0; j < arr.length - 1 - i; j++) { // 当前趟要比较的次数
            if (arr[j] > arr[j+1]) {        // 相邻元素两两比较
                var temp = arr[j];              // 元素交换
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

代码与图片配合食用更加~

Untitled

改进版（JS）

// 改进冒泡排序
function bubbleSort1(arr) {
    let i = arr.length - 1;

    while (i > 0) {
        let pos = 0;
        for (let j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                pos = j;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        i = pos;
    }
    return arr
}

根据上述代码，我们每一轮冒泡需要的结果就是把最大的数通过冒泡放到最后，
然后缩小下一轮需要冒泡的数组的范围（未优化的方案中数组范围只缩小了一位），
但是实际上我们每一轮冒泡后可能会出现后面的几个数都有序的情况，
这个时候我们完全可以再缩小一点下一次需要冒泡的数组的范围
（不然下一轮冒泡到最后发现最大的数本来就在最后，此次冒泡就是多余的）。那怎么确定这个i值呢？

举个栗子：
[a[0],...,a[j],a[j+1],...,a[i]]
如果某一次冒泡比较中a[j]>a[j+1]
交换两值，此时a[j+1]大于a[0]到a[j]的任何值（a[0]到a[j]还是无序的）
如果再接下来的冒泡中满足a[j+1]到a[i]有序，即不做任何交换操作（a[j]和a[j+1]是最后一次交换操作）
那我们下一轮只需要对a[0]到a[j]的无序数组进行冒泡排序，j就是下一轮循环的i值

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤