阅读 948

【小小前端】前端排序算法第一期(冒泡排序、选择排序、插入排序)

算法分类

十种常见排序算法可以分为两大类:

非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。

线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。

算法复杂度

相关概念

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。

时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。

冒泡排序(Bubble Sort)


原理:

比较两个相邻的元素,将值大的元素交换到右边

算法描述

  1. 比较第一位与第二位,如果第一位比第二位大,则交换位置
  2. 继续比较后面的数,按照同样的方法进行比较,到最后一位的时候,最大的数将被排在最后一位
  3. 重复进行比较,直到排序完成,注意由于上一次排序使得最后一位已经是最大的数,所以每次排序结束之后,下一次比较的时候可以相应的减少比较数量

动图演示

代码解析

    let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
    let flag;
    let len = arr.length;
    let num1 = 0; // 比较的次数
    let num2 = 0; // 交换的次数
    // 有15个数,只需要选出14个最大的数,最后一个数就是最小的,不用进行比较
    for(let i = 0; i < len -1 ; i++){
        // 每次i变化之后最大的值已经排序到最后一位,无需对最后一位进行比较,所以j的最大值为len-i-1
        for(let j = 0; j < len - i - 1; j++){
            num1 += 1;
            // 如果当前位置的数比下一位置的数大,则交换位置
            if(arr[j] > arr[j+1]){
                num2 =+ 1;
                flag = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = flag
           }
        }
    }
    console.log(arr,num);
复制代码

输出的结果为:

计数器num1和num2的值分别为:105和46

从代码中看出,排序过程中,所需要的临时变量一直都没有变化,因此空间复杂度为O(1);代码进行了两次for循环且是嵌套循环,因此时间复杂度为O(n²)。

冒泡排序的最优情况是原数组默认正序排序,此时比较的次数num1仍为105,而交换次数num2为0,此时的时间复杂度仍然为O(n²),那么为什么前面的复杂度表格中说是O(n)呢?经过一番研究发现,需要对上述代码进行简单优化。

如果排序的数组是:[1,2,3,4,5],此时完全符合最优复杂度情况,当我们进行第一次循环发现,两两相邻的数据一次都没有进行交换,也就是说所有的数都比前一个数大,此时就是正序,无需再进行下次排序,所以我们只需要加上一个变量进行判断:

    // 初始未产生交换
    let isSwap = false;
    for(let i = 0; i < len -1 ; i++){
        // 每次i变化之后最大的值已经排序到最后一位,无需对最后一位进行比较,所以j的最大值为len-i-1
        for(let j = 0; j < len - i - 1; j++){
            num1 += 1;
            // 如果当前位置的数比下一位置的数大,则交换位置
            if(arr[j] > arr[j+1]){
                num2 =+ 1;
                isSwap = true;
                flag = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = flag
           }
        }
        // 如果产生交换,直接结束循环
        if(!isSwap){
            return
        }
    }
复制代码

当产生交换时,isSwap变成true,第一次循环结束之后,如果isSwap如果还是false表示未经过交换,数组已经是正序,无需继续排序,此时的时间复杂度为O(n)

在比较过程中只判断了大于后一个数,如果两个数相等无需交换,所以冒泡排序是稳定的排序。

选择排序(Selection Sort)


原理

将序列分为未排序和已排序,从未排序序列中找到最小的数,放到无序序列起始位置,然后继续从剩余未排序序列中继续寻找最小值

算法描述

  1. 初始无序序列为待排序序列,有序序列为空
  2. 从无序序列中找到最小值,放到无序序列起始位置,也就是和起始位置交换
  3. 将无序序列起始位向后推一个位置,继续2步骤

动图演示

代码解析

        // 选择出无序序列中最小的值放到无序第一位
        let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
        let len = arr.length;
        let minIndex;
        let flag;
        let num1 = 0; // 比较次数
        let num2 = 0; // 交换次数
        for(let i = 0; i < len - 1;i++){
            // 每次选择最小值之后,无序区的开始位置往后推1
            minIndex = i;
            // j循环到最后一位,选择出当前无序数组中数值最小的索引值
            for(let j = i + 1; j < len;j++){
                num1 += 1;
                if(arr[minIndex]>arr[j]){
                    minIndex = j;
                }
            }
            num2 += 1;
            flag = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = flag;
            
        }
        console.log(arr,num1,num2)
复制代码

输出结果为:

计数器num1和num2的值分别为:105和14

也就是说,选择排序的比较次数和冒泡排序未优化时一样,而交换的次数只有14次

再举刚刚的栗子:[1,2,3,4,5],正序序列,无需进行任何交换,我们对最后交换代码进行优化:

if(minIndex == i){
    num2 += 1;
    flag = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = flag;
}
复制代码

此时没有发生数据交换。

其实从代码中可以看到,无论如何,选择排序总会经过N^2/2次比较,而受原始数列影响,交换的次数最大为n-1,最小次数为0。

因此选择排序时间复杂度总为:O(n平方),空间复杂度为:O(1)

选择排序是不稳定的,为什么这么说,看个栗子:[5,3,8,5,2],好了不说也能看出来了。

插入排序(Insertion Sort)


原理

构建有序序列,对于未排序的数据,从有序序列后向前扫描,找到相应位置插入

动图演示

代码实现

        let arr = [3, 45, 16, 8, 65, 15, 36, 22, 19, 1, 96, 12, 56, 12, 45];
        let len = arr.length;
        // 定义当前未排序数据起始位置值也就是即将插入的数据
        let currentValue;
        // 有序序列遍历位置
        let preIndex;
        let num1 = 0; // 比较次数
        let num2 = 0; // 交换次数
        for(let i = 1;i < len; i++){
            // 定义原始数据第二位为未排序数据第一位,默认原始数据第一位已排序
            currentValue = arr[i];
            // 当前有序序列最大索引
            preIndex = i - 1;
            // 当索引大于等于0且当前索引值大于需要插入的数据时
            for(let j = preIndex;j>=0;j--){
                // 第一次比较,如果有序序列最大索引值其实就是待插入数据前一位,比待插入数据大,则后移一位
                num1+=1;
                if(arr[preIndex]>currentValue){
                    arr[preIndex+1] = arr[preIndex];
                    preIndex --;
                    // 索引减1,继续向前比较
                }
            }
            // 当出现索引所在位置值比待插入数据小时,将待插入数据插入
            // 为什么是preIndex+1,因为在while循环里面后移一位之后,当前索引已经变化
            num2 += 1;
            arr[preIndex+1] = currentValue;
        }
        console.log(...arr,num1,num2)
复制代码

输出的结果为:

计数器num1和num2的值分别为:105和14

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

在时间复杂度上,如果按照上述写法,执行的次数依次为,1,2,3....n-1,因此时间复杂度为O(n²)

冒泡排序出现了优化之后最优复杂度变小的情况,看看前面的表格,插入排序的最优时间复杂度为O(n),那么这又是什么原因呢?

我们看看判断待插入值是否小于当前索引位置值的地方,用了一个for循环和一个if,我们能不能改写一下呢?

        while(preIndex>=0&&arr[preIndex]>currentValue){
            arr[preIndex+1] = arr[preIndex];
            preIndex --;
        }
复制代码

这样看,如果在正序情况下:[1,2,3,4,5],每次比较都不会进入while循环,因此只执行了n-1次比较操作,因此此时时间复杂度为O(n),那么最坏复杂度其实也就是逆序情况了,需要执行1,2,3...n次,因此最坏时间复杂度为O(n²)。

总结

综合比较一下最简单的三种排序方法:

选择排序在冒泡排序上做了优化,冒泡排序两两比较每一轮选出一个最大值,而选择排序则从序列中直接选择出最小值插入无序序列首部(进行交换),相对于冒泡排序减少了不必要的换位操作。

插入排序在思想上和选择排序差不多,选择排序是从无序序列中找出最小值,与无序序列的首位进行交换,从而生成一个有序序列,而插入排序则从无序序列中直接选出首位,将首位与有序序列进行比较,插入相应的位置。

使用场景

对于一般工作来说,这三种使用没什么体验上的差距

如果非要选择的话,插入排序比选择排序少一些比较的次数,但选择排序有时候比插入排序少挪动次数,建议数据较大时用插入排序,数据量较小时可以用选择排序。(其实这俩差不多--)

参考

新手上路请多指教,如有错误,轻喷

下集预告

【小小前端】前端排序算法第二期(绕人的希尔排序)