基本排序算法

在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。

这里简单的介绍三种最基本的排序，分别是：冒泡排序、选择排序以及插入排序

排序的过程中，经常要用到交换元素位置，故抽离为公共函数 swap。

// 交换位置
export function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

冒泡排序

冒泡排序是最简单的排序，一一对比相邻的两个数，顺序不对就交换过来，这样子，每一轮最大的值总会慢慢的被交换到最右侧。所以才会叫冒泡排序

描述

假设数组长度为 n

• 比较相邻的两个数，如果第 1 个大于第 2 个，就交换位置
• 重复第 1 步，一轮下来最大值被交换到第 n 个位置，也就是最右侧
• 开启新一轮，重复 1~2 步，最大值会被冒泡到第 n-1 个位置
• 重复上述步骤，直到所有都排序好

例子：

对 3, 1, 5, 2, 4 进行排序

1,3,5,2,4  3 > 1 ,交换位置
1,3,5,2,4  3 < 5 ,不变
1,3,2,5,4  5 > 2 ,交换位置
1,3,2,4,5  5 > 4 ,交换位置,第一轮结束
1,3,2,4,5  1 < 3 ,不变
1,2,3,4,5  3 > 2 ,交换位置
1,2,3,4,5  ...依次对比
1,2,3,4,5  ...
1,2,3,4,5  ... 结束

代码实现

// 冒泡排序
export function bubbleSort(array) {
    for (let i = array.length - 1; i >= 1; i--) {
        let hasSwap = false;
        for (let j = 0; j <= i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                hasSwap = true;
            }
        }
        if (!hasSwap) {
            // 这里用于优化，如果某一轮之后，没有进行任何交换，说明已经排序完成了，所以退出循环
            break;
        }
    }
}

效果演示

https://global.chen4342024.co...

小结

冒泡算法是比较慢的排序之一，也是最容易实现的算法之一。

复杂度

• 稳定性：稳定
• 时间复杂度： 平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)
• 额外空间复杂度 O(1)

选择排序

选择排序是指每一轮从数组中取出最小值，然后跟第一个元素交换位置。然后再找出第二个最小值，跟第二个元素交换位置，。。。以此类推。直到倒数第二个位置

例子

对 3, 1, 5, 2, 4 进行排序

// 这里只展示每一轮的结果
3 1 5 2 4   //开始
1 3 5 2 4   //第 1 轮
1 2 5 3 4   //第 2 轮
1 2 3 5 4   //第 3 轮
1 2 3 4 5   //第 4 轮

代码实现

// 选择排序从开头开始，找出最小的值，放在第一个位置
// 有点类似打扑克拍的时候，抽取每一张最小的放在最左边
export function selectSort(array) {
    for (let i = 0; i < array.length - 1; i++) {
        let minIndex = i;
        let min = array[i];
        for (let j = i + 1; j < array.length; j++) {
            if (array[j] < min) {
                min = array[j];
                minIndex = j;
            }
        }
        swap(array, i, minIndex);
    }
}

效果演示

https://global.chen4342024.co...

复杂度

• 稳定性：不稳定
• 时间复杂度： O(n^2)
• 额外空间复杂度 O(1)

插入排序

插入排序的思想是，依次从数组中未排序的部分，取出数据，然后插入到已排序的部分。直到清空未排序的部分

描述

假设数组长度为 n , 从第 2 项开始

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素大于新元素，将该元素移到下一位置；
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤 2~5。

代码实现

export function insertSort(array) {
    for (let i = 0; i < array.length; i++) {
        let temp = array[i];
        let j = i;
        while (j > 0 && array[j - 1] > temp) {
            // 将所有大于temp的往右移
            array[j] = array[j - 1];
            j--;
        }
        array[j] = temp;
    }
}

效果演示

https://global.chen4342024.co...

复杂度

• 稳定性：稳定
• 时间复杂度：平均 O(n^2) 、 最坏 O(n^2) 、最好 O(n)
• 额外空间复杂度 O(1)

效果演示（汇总）

https://global.chen4342024.co...

总结

这三种最基本的排序算法的复杂度非常相似，从理论上来说，它们的执行效率也应该差不多。

在实际使用中，如果需要排序的数据比较多，是不推荐使用这 3 种排序的。毕竟他们的效率都不太理想

在实际应用中，应该选择高级排序算法： 快速排序 ...

在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。大概是冒泡/选择排序的快 1 倍

这是因为 插入排序需要比较的次数是 1+2+3+..+n = n * (n-1) /2,这是最坏的情况，大部分时候并不需要全部比较，所以平均下来只需要 n*(n-1)/4

而冒泡/选择排序都需要n * (n-1)/2,所以平均下来，插入排序大概是冒泡/选择排序的快 1 倍