亚里士多德把知识分为三类:第一类是「经验」，会做但不知道为什么这么做是对的；第二类是知其然又知其所以然的「技术」，它来源于经验，是通过对经验的总结和归纳所形成的一般化理论；第三类是没有用的、自己为自己而存在的知识就是科学
?前言大家好，我是柒八九。因为，最近在看Vue3源码分析，发现无论React还是Vue，在框架层面，为了实现特定的场景，它们为我们封装了很多比较复杂的逻辑。比如，
针对VirtualDom的Diff算法中树的遍历(DSF);还有针对Vue3的双端Diff中在查看可复用节点时，用到的「最小递增子序列」算法；针对指定「DSL」(领域特定语言)的编译、转换处理中用到stack数据结构进行token的匹配针对Vue中内置组件KeepAlive中用到的缓存中用到的「LRU」(最近最久未使用)等等「透过现象看本质」，无论是如何高深的算法或者思路，其实都是利用合适的数据结构对其遍历和筛选处理。而今天我们就来利用一篇文章的时间，来讲讲在平时工作中或者面试中比较常见的「排序算法」。
排序算法有很多，而我们只总结和处理我们平时接触到，并用到的，也算是一个针对排序算法的「初级」的汇总和总结。(大神勿喷)
「时间不早了，干点正事哇」。(郭德纲语言包)针对居中我们有一个「打油诗」
排序算法种类多，常规算法要记牢「交换排序」找「主元」(pivot)，Bubble/Quick齐上阵Bubble双层循环O(n2)，主元藏于内层循环arr[j]Quick「分治递归」O(nlogn),partition「中值」效率高「插入排序」找「哨兵」(sential),Insertion/Shell双胞弟，Insertion区间分「两段」外层未排i∈[1,len)内层已排j∈[0,i-1],sential初始为arr[1]Shellwhile(增量=1),内核照抄Insertion只将i=1/j=i-1改为i=t/j=i-t「选择排序」找「极值的序号」(minIndex),Selection/Heap一路数Selection区间分「两段」外层已排i∈[0,len-1)内层未排j∈[1,len)minIndex初始为i且为「0」「归并排序」DC思想好找前后区间起始位置i=lo/j=mid+1找修改原数组的位置k=lo复制原数组copy数据移动找「退出条件」lo=hi找「中值」mid=lo+((hi-lo)1)递归双区间「先分后治」分用「递归」来处理治阶段文章概要交换排序SwapSort冒泡排序BubbleSort快排序QuickSort插入排序InsertionSort插入排序InsertionSort希尔排序ShellSort选择排序SelectionSort归并排序MergeSort知识点简讲复杂度?「复杂度」是衡量代码运行效率的重要「度量」因素
?复杂度是一个关于输入数据量n的函数,它有两个特点：
复杂度与具体的「常系数无关」多项式级的复杂度相加的时候，「选择高者」作为结果O(1)也是表示一个特殊复杂度:其含义为某个任务通过「有限可数」的资源即可完成。
而复杂度又可以分为
「时间复杂度」:与「代码结构」有着非常紧密的关系「空间复杂度」:与「数据结构」的设计有关针对「时间复杂度」，有几个经验性的结论：
代码结构时间复杂度「顺序结构」的代码O(1)「二分查找」/采用分而治之的「二分策略」O(nlogn)简单的for循环O(n)两个「顺序执行」的for循环O(n)+O(n)=O(2n)，即O(n)两个「嵌套的」for循环O(n2)针对在平时算法学习和工作中，我们需要有一个意识：「时间昂贵、空间廉价」。所以，如果遇到复杂度比较高的情况，需要对其进行降阶处理。常规步骤如下：
先暴力解法：在没有任何时间、空间约束下，完成代码任务的开发无效操作处理：将代码中的无效计算、无效存储剔除，降低时间或空间复杂度「时空转换」：设计合理数据结构，完成时间复杂度向空间复杂度的转移针对算法复杂度，其实有一个「大O表示法」，而上面的介绍只是简单的把一些概念给罗列了一下，如果对如何计算和各种复杂度的分类可以参考一些专业的书。
原地排序和稳定性?「原地排序」：指在排序过程中「不申请多余的存储空间」，只利用原来存储待排数据的存储空间进行比较和交换的数据排序
??「稳定性」：能保证两个相等的数，经过排序之后，其在序列的「前后位置顺序不变」（A1=A2，排序前A1在A2前面，排序后A1还在A2前面）
?两个变量值互换现在，存在变量a=1/b=2,想要将它们的值「互换」。
一个信手拈来的代码。
leta=1,b=2;lettemp;temp=a;a=b;b=temp;
「有问题，没有问题，但是不够优雅」。其实，我们可以不「借用」第三个零时变量就可以将两个变量的值，直接替换了。
我们可以利用位运算的「异或运算符」(^),连续对两个数a和b进行「三次异或运算」，a^=b;b^=a;a^=b;，可以互换它们的值。
leta=1,b=2;a^=b;b^=a;a^=b;
利用^处理变量互换，倒是省去了，temp变量了，但是针对位运算的操作，让代码看起来很「晦涩难懂」。
我们可以ES6的一些特性做点事。而这次轮到了解构。
leta=1,b=2;[a,b]=[b,a];
就是这么神奇。
util工具函数为了篇幅能够紧凑，我们将本文中用到的一些比较常规的函数，汇集到这里。
用于数组数据交换functionswap(arr,i,j){return[arr[i],arr[j]]=[arr[j],arr[i]];}用于数据对比
constCompare={LESS_THAN:-1,BIGGER_THAN:1};functiondefaultCompare(a,b){if(a===b)return0;returnab?Compare.LESS_THAN:Compare.BIGGER_THAN;}1.交换排序SwapSort?
「交换排序」最主要的特点就是找主元pivot
?冒泡排序BubbleSortfunctionBubble(arr){letlen=arr.length;if(len2)returnarr;//处理边界值for(leti=0;ilen-1;i++){//注意j的范围[0,len-i-1)=左关右开for(letj=0;jlen-i-1;j++){if(arr[j]arr[j+1])swap(arr,j,j+1);}}returnarr;}
上面我们只是构建了一个最简单的BubbleSort，其实还有各种优化的空间。
案例分析假设，我们现在有arr=[5,4,3,2,1]的数组，要求对该数组，进行排序，使其数据「升序排列」。
通过，一个简单的例子，我们再继续分析，上面的的一些关键点。BubbleSort本质上就是一种SwapSort,而交换排序最关键的点，就是需要在每次遍历过程中寻找「主元」(pivot)。而冒泡排序中，外层循环只是控制，需要最多循环的次数，数据对比和交换是在内层循环中处理。
也就是说
?「冒泡排序」中内层循环arr[j]是「主元」
?优化处理在上面的例子中，我们只是构建了一个最简单的例子，其实，针对上面的例子，还有很多需要改进的地方。比如，
在比对的时候，只有在「主元」满足交换条件的时候，才进行后续处理。按升序来举例，只有满足arr[j]arr[j+1]，才进行数据交换。而对于一些，「天生升序」的序列，没必要每个数据都进行条件判断。此时，我们需要在外层循环定义一个变量isSorted(默认值为true)来标识。通过配置，能满足「升序/降序」排序直接上代码了。
functionBubble(arr,