前端基本排序算法总结

喜欢ヅ旅行 2024-04-17 06:29 77阅读 0赞

> 前言

hellow大家好久不见，原本定于上周发的算法文章也因为电脑报废没有发送成功，这周刚好入手新电脑就着手发送文章了。

好了废话不多说，进入这次的主题基本排序算法，首先呢先说明一下虽然排序算法不是面试时必问的题目不过也可以排在前10的位置，另外呢我们日常会经常用到排序算法，我会举一些例子进行说明，就这样下面开始今天的讲解吧。

> 内容

### 冒泡排序 ###

怎么么说呢，应该大部分人不管学习什么编程语言的接触到的第一个或者说第一种排序算法应该就是冒泡排序了吧，这个应该没有异议。

废话不多说直接甩个例子：

5 1 4 2 8
    复制代码

经过一次循环后排列变成

1 5 4 2 8
    复制代码

前面两个数字互换，接下来：

1 4 5 2 8
    复制代码

这里不知道大家看出来没有，永远都是把小的数字往前移动，也就是说对比是两两对比小的往前走，大的往后，没有的话跳过。

1 4 2 5 8
    复制代码

这里可以看出来互换快要完成了，需要进行最后一次对比就能出来结果。

1 2 4 5 8
    复制代码

最终顺序就是上面所示，可能这样不是很直观没关系，我放个图片就能比较直观的观察了。

这里借用了一张图片进行说明，其实基本思想就是逐个的比较，下面是实现的代码：

这边有两点要注意：

1.外层循环，从最大值开始递减，因为内层是两两比较，因此最外层当>=2时即可停止；

2.内层是两两比较，从0开始，比较inner与inner+1，因此，临界条件是inner < outer -1

所以这边在交换值的时候用了es6的解构来做的，\[arr2\[0\],arr2\[1\]\] = \[arr2\[1\],arr2\[0\]\]如果不懂的同学可以去看看阮一峰老师的博客，对es6的讲解很深入，这里就不一一赘述了。下面贴上链接大家有于兴趣可以去看下。

[ECMAScript 6 入门 (阮一峰)][ECMAScript 6 _]

### 选择排序 ###

选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后。

同样借用一张图说明情况，外层循环从0开始到length-1， 然后内层比较，最小的放开头所以公式即为：

与上述一致同样有两点需要注意：

1.外层循环的i表示第几轮，arr\[i\]就表示当前轮次最靠前(小)的位置；

2.内层从i开始，依次往后数，找到比开头小的，互换位置即可

### 插入排序 ###

插入排序核心--扑克牌思想： 就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边，继续接，可能是中间数，就插在中间....依次，其实这样说大家可能还是不是很理解，简单来讲就是以第一个插入的数为基数，小的往左放大的往右放，然后不断循环基数如果第一个最小，那么就从第二个开始比较，依次循环。

同样借用一张图进行说明：

这边简单唠叨两句：

其实每种算法，主要是理解其原理

包括比如面试的时候面试官想要你回答的是过程和结果没错但是，要注意一点那就是思想核心思想这点如果能表述清楚就是一个很大的加分项，当然了结果一样重要。

这里分析一下：

1. i是外循环，依次把后面的数插入前面的有序序列中，默认arr\[0\]为有序的，i就从1开始

2. j进来后，依次与前面队列的数进行比较，因为前面的序列是有序的，因此只需要循环比较、交换即可

3. 注意这里的break，因为前面是都是有序的序列，所以如果当前要插入的值arr\[j\]大于或等于arr\[j-1\]，则无需继续比较，直接下一次循环就可以了。

### 快速排序算法 ###

这里提前说两句，快排算法其实稳定性不一定算是最好的，比如A、B两个物品名字什么的都一样排序的时候A在前面B在后面，但是用了快排之后可能顺序就会对调，但是名字都一样这样是没错的。

其实呢日常如果我们不是用数据量较大的表单演示的话那么建议还是使用冒泡之类的基础排序这样更可靠些，至于快排如果追求优化的话也可以用，但是适用于不同业务场景的用不同的排序方法吧。

好了不多说了下面简单说下快排，快速排序可以说是对于前端最最最最重要的排序算法，没有之一了，面试官问到排序算法概率绝对是排序算法中的第一。

所以快排是什么呢？

快排是处理大数据最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直至所有数据都是有序的。

简单说： 找到一个数作为参考，比这个数字大的放在数字左边，比它小的放在右边； 然后分别再对左边和右变的序列做相同的操作:

1. 选择一个基准元素，将列表分割成两个子序列；

2. 对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值的后面；

3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2

同样借用一张图进行说明

### 希尔排序 ###

希尔排序是插入排序的改良算法，但是核心理念与插入算法又不同，它会先比较距离较远的元素，而非相邻的元素。

下面借用一张图进行说明吧

实现希尔排序之前先看下插入排序：

现在，不同之处是在上面的基础上，让步长按照3、2、1来进行比较，相当于是三层循环和嵌套。

insert(arr,[3,2,1]);
    function shellSort(arr,gap) {
        console.log(arr)//为了方便观察过程，使用时去除
        for(let i = 0; i<gap.length; i++) {  //最外层循环，一次取不同的步长，步长需要预先给出
            let n = gap[i]; //步长为n
            for(let j = i + n; j < arr.length; j++) { //接下类和插入排序一样，j循环依次取后面的数
                for(let k = j; k > 0; k-=n) { //k循环进行比较，和直接插入的唯一区别是1变为了n
                    if(arr[k] < arr[k-n]) {
                        [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                        console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
                    } else {
                        continue;
                    }
                }
            }
        }
        return arr;
    }
    
    复制代码

直接看这个三层循环嵌套的内容，会稍显复杂，这也是为什么先把插入排序写在前面做一个对照。 其实三层循环的内两层完全就是一个插入排序，只不过原来插入排序间隔为1，而希尔排序的间隔是变换的n， 如果把n修改为1，就会发现是完全一样的了。

运行一下看看：

var arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];
    var gap = [3,2,1];
    console.log(shell(arr,gap))
    复制代码

结果为\[0,2,3,4,5,6,8,9,19,23,45,55\] ，其实想要看细节的小伙伴可以打印看看，同时也能明白其中的原理。

### 时间复杂度总结 ###

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th style="text-align:center;">平均时间复杂度</th> 
   <th style="text-align:right;">最坏时间复杂度</th> 
   <th style="text-align:right;">空间复杂度</th> 
   <th style="text-align:right;">是否稳定</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td style="text-align:center;">O(n²)</td> 
   <td style="text-align:right;">O(n²)</td> 
   <td style="text-align:right;">O(1)</td> 
   <td style="text-align:right;">是</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td style="text-align:center;">O(n²)</td> 
   <td style="text-align:right;">O(n²)</td> 
   <td style="text-align:right;">O(1)</td> 
   <td style="text-align:right;">不是</td> 
  </tr> 
  <tr> 
   <td>直接插入排序</td> 
   <td style="text-align:center;">O(n²)</td> 
   <td style="text-align:right;">O(n²)</td> 
   <td style="text-align:right;">O(1)</td> 
   <td style="text-align:right;">是</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td style="text-align:center;">O(nlogn)</td> 
   <td style="text-align:right;">O(n²)</td> 
   <td style="text-align:right;">O(logn)</td> 
   <td style="text-align:right;">不是</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td style="text-align:center;">O(nlogn)</td> 
   <td style="text-align:right;">O(n^s)</td> 
   <td style="text-align:right;">O(1)</td> 
   <td style="text-align:right;">不是</td> 
  </tr> 
 </tbody> 
</table>

#### 是否稳定 ####

如果不考虑稳定性，快排似乎是接近完美的一种方法，但可惜它是不稳定的。 那什么是稳定性呢？

通俗的讲有两个相同的数A和B，在排序之前A在B的前面，而经过排序之后，B跑到了A的前面，对于这种情况的发生，我们管他叫做排序的不稳定性，而快速排序在对存在相同数进行排序时就有可能发生这种情况。

/*
    比如对(5，3A，6，3B ) 进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成  
    	（3B，3A，5，6）
    所以说快速排序是一个不稳定的排序
    /*
    复制代码

稳定性有什么意义？ 个人理解对于前端来说，比如我们熟知框架中的虚拟DOM的比较，我们对一个

*  列表进行渲染，当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。

#### 辅助记忆 ####

时间复杂度记忆

冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)(一遍找元素O(n)，一遍找位置O(n)）

快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)(一遍找元素O(n)，一遍找位置O(logn))

稳定性记忆-“快希选堆”（快牺牲稳定性）

> 总结