所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

冒泡排序

冒泡排序是入门级的算法，但也有一些有趣的玩法。通常来说，冒泡排序有三种写法：

一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；

基础算法

空间复杂度为 $O(1)$，时间复杂度为 $O(n^2)$

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len-1; i++){
        for (let j = 0; j < len-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr
}
复制代码

最外层的 for 循环每经过一轮，剩余数字中的最大值就会被移动到当前轮次的最后一位，中途也会有一些相邻的数字经过交换变得有序。总共比较次数是 (n-1)+(n-2)+(n-3)+…+1(n−1)+(n−2)+(n−3)+…+1。

第二种写法是在基础算法的基础上改良而来的：

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        let isSwap = false
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                isSwap = true
            }
        }
        if (!isSwap) {
            break;
        }
    }
    return arr;
};
复制代码

空间复杂度为$O(1)$;时间复杂度为 $O(n^2)$-最好为O(n);

最外层的 for 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是：如果一轮比较中没有发生过交换，则立即停止排序，因为此时剩余数字一定已经有序了。

选择排序

选择排序的思想是：双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

基础算法

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        let minIndex = i
        for (let j = i+1; j < len; j++) {
            if (arr[i] > arr[j]) {
                minIndex = j
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
};
复制代码

二元选择排序-优化

选择排序算法也是可以优化的，既然每轮遍历时找出了最小值，何不把最大值也顺便找出来呢？这就是二元选择排序的思想。

使用二元选择排序，每轮选择时记录最小值和最大值，可以把数组需要遍历的范围缩小一倍。

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len / 2; i++) {
        let minIndex = i;
        let maxIndex = i;
        for (let j = i + 1; j < len-i; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }
        if (minIndex === maxIndex) break;
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        if (maxIndex === i) {
            maxIndex = minIndex;
        }
        const lastIndex = len - i - 1;
        [arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]];
    }
    return arr; 
};
复制代码

插入排序

插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。

插入排序有两种写法：

• 交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
• 移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。

交换法插入排序

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i;
        while (j >= 1 && arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--
        }
    }
    return arr;
};
复制代码

当数字少于两个时，不存在排序问题，当然也不需要插入，所以我们直接从第二个数字开始往前插入。

移动法

我们发现，在交换法插入排序中，每次都要交换数字。但实际上，新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说，它刚换到新的位置上不久，下一次比较后，如果又需要交换，它马上又会被换到前一个数字的位置。

由此，我们可以想到一种优化方案：让新插入的数字先进行比较，前面比它大的数字不断向后移动，直到找到适合这个新数字的位置后再插入。

这种方案我们需要把新插入的数字暂存起来，代码如下：

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i-1;
        let cur = arr[i];
        while (j >= 0 && cur < arr[j]) {
            arr[j+1] = arr[j]
            j--;
        }
        arr[j+1] = cur
    }
    return arr;
};
复制代码