这篇文章主要想讲讲数据结构，但是结合上一篇文章的时间复杂度，我觉得这篇文章会写一些基本的排序算法，再分析一下它的复杂度就好了。概述如果你经常做一些算法题，你可能会发现80%以上的题都会用到排序。而且，也许你在学习算法时首先遇到的就是排序！排序非常重要。可以说，掌握了复杂度分析和一些基本的排序，就会更容易处理大量的前端数据操作问题。当然，如果掌握一些基本的数据结构就更好了。不过排序算法真的太多了，很可能有些连名字都没听过，比如猴子排序、睡眠排序、鸡尾酒排序、鸽子洞排序、面条排序，还有一些不切实际的波哥排序、珠子排序、ETC。。所以这里我只说说众多排序算法中的一小部分，也是最基本最实用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。简介说到算法，就不得不说说这个算法的优缺点，排序算法也不例外。我们一般从这几个方面来分析一个排序算法：1.执行效率2.稳定性3.内存消耗首先说执行效率。如果你读完我的上一篇文章，复杂性分析应该给我一些想法。说白了，就是分析这个排序算法的最佳、最差和平均时间复杂度。为了进一步优化，我们会继续分析系数，常数，时间复杂度的低阶，因为O(logn)的排序不一定比O(n^3)好，因为我知道logn<arr[j+1]){让缓存=arr[j];arr[j]=arr[j+1];arr[j+1]=cache}j++}i++}}上面的代码可以改进，即在某次排序过程中（while循环的第二层），如果整个循环没有数据交换，则表示这组数据是完全有序的，可以直接返回；方法是声明一个是否发生交换标志flag=false，当有数据交换时，我们将其设置为true，如果循环结束后该标志仍然为false，则可以退出循环，否则重新设置为false，进入下一个while循环。我们分析了优化版冒泡排序的复杂性。第一最佳时间复杂度->1,2,3,4,5复杂度为O(n)最坏时间复杂度5,4,3,2,1。复杂度为O(n^2)这两个很简单，所以我不会做更多的分析。那么平均时间复杂度呢？我在上一篇文章中说过，平均时间复杂度是加权平均期望时间复杂度。我先详细分析一下冒泡排序是怎么计算的，后面就不一一分析了。如果这个优化的冒泡排序用概率的分析方法很复杂，我们可以换个角度思考问题。其实排序其实就是变无序为有序，所以这里引入两个新的概念：有序度，逆序度Thedegreeoforder有序度就是数组中具有有序关系的元素对的个数，也就是说，如果jarr[j+1]){letcache=arr[j];arr[j]=arr[j+1];arr[j+1]=cache}，正好发生了一次正序度+1，逆序度-1。例如5、4、1、3、2、6的初始订单度为6，全订单度为15，则必须有15-6=9次交易所才能完成订单。如果是n条数据呢？那么最好的情况是0次交换，最坏的情况是n(n-1)/2。那么平均情况就是n(n-1)/4次交换。注意这里只是交换，每次都要进行比较操作。但最坏的只是n(n-1)(n-2)...21<=n^2。所以我们可以说平均时间复杂度是O(n^2)。虽然不严格，但是比用概率和期望的方法进行定量分析要容易的多！鸡尾酒排序这种排序用的不多。其实就是双端冒泡，即第一次找到最大值放在后面，下一轮再找最小值放在前面。例子3,1,4,9,5。第一次排序后，我们把9放在最后。第二次，我们找到最小值1放在最前面，依次旋转。直到完全安排好，看看就知道了。插入排序在说插入排序之前，先说一个场景。排队的时候，假设已经按照大小身高排好了，这时候多了一个新同学，怎么办？显然他可以从头开始比较，当你遇到一个比你矮的人时，回头看，直到找到第一个比你高的人，然后站在他的面前。图：从图中可以看出，假设要排序的是一个数组，那么我们可以把它分成两部分，一个是已排序的部分，一个是未排序的部分。或者如果是三部分，则多插入一个元素。总之，思路是一样的。当一些没有排列的元素长度为0时，说明数组完全有序，排序算法完成。最初，排列的区间中只有一个元素，即图中的3。每次从未排列的区间中取出一个元素插入到已排列的区间中，从后往前依次比较。如果满足条件，则直接插入到当前位置。否则，被比较的元素向后移动一个位置（腾出空间），然后继续比较。代码实现（从小到大排列）functionsort(arr){letl=arr.length;//因为我们已经假设第一个元素是排列好的，所以i从1开始leti=1,jfor(;i=0;j--){//如果选中的元素大于前一个元素，证明已经排好if(target>arr[j]){break;}else{//否则，前一个元素向后移动，为目标元素留出位置arr[j+1]=arr[j]}}//最后在空位置插入arr[j+1]=target;}}动态演示分析：首先，插入排序是稳定排序算法吗？我们在代码中可以看到，对于两个相等的元素，我们并没有交换位置，而是认为这个元素的排序已经完成（也就是找到了插入位置），所以插入排序是一种稳定的排序算法。插入排序是就地排序？自始至终，我们都没有申请额外的存储空间，所以插入排序是一种就地排序算法。插入排序的时间复杂度是多少？首先是最好的时间复杂度（初始排序），然后我们每次只比较一次位置就可以确定，一共n次就可以完全排序，复杂度O(n)最坏情况时间复杂度（初始完全逆序），那么每次都要比较当前下标之前的所有元素，即总共有1+2+...+n=(n+1)n/2。那一般情况呢？我们同样用有序度来分析，假设全序度为20，初始值为5。当我们比较位移时，每位移一次，逆序度为-1，度顺序是+1。和冒泡排序分析一样可以平均时间复杂度也是O(n^2)选择排序selectionsorting，顾名思义，每次选择排序都是有针对性的，也就是每次选择最小值在前面或最大值放在最后。图：直接代码：functionsort(arr){letl=arr.length;让minIndex=0;for(leti=0;i插入排序我们上面实现的算法是直接插入排序，也就是从来不在每次排列的区间内取一个元素，从后面到前面排列的区间进行比较正面。如果数据量很大，范围内排列的元素越多，我们可能遍历的次数就越多。例如18,52,66,11....{10000}......999,1当我们排列最后一个元素1时，我们需要将插入指针从排列的范围末尾移动到所有前面的方式，在大量数据的情况下不是很高。其实我们知道已经排列在区间内的数据是有序的，那么我们就可以使用二进制比较的方法。比如5、7、8、10、12、16、18、19、22就是已经排列好的范围。这时候我们从未排列的区间中取出一个数。如果是9，则直接与排列好的区间arr[(0+i)/2]，即12进行比较，9<12，说明一定在5-10的区间，即arr[0-(0+i)/2]，继续比较。插入它直到它找到合适的位置。这样，我们每次都将搜索范围缩小一半，实现起来也不难。如果你有时间，你可以自己实现。其实我想在下一篇写这个排序算法，因为我们可以发现，上面所有算法的平均时间复杂度都是O(n^2)，大量数据的数据处理似乎还是性能低下。下一篇会讲到O(nlogn)的排序算法，希尔排序的平均时间复杂度也是O(nlogn)，但是因为是优化版的插入，所以包含了我下一篇文章的思路将讨论分而治之。为什么希尔排序是插入排序的优化版本？因为它解决了最重要的影响插入排序效率的特性。插入排序一次只能移动一位数据。为什么这会影响效率？请看上面的插入和半排序。刚才说了，如果最后一位刚好是最小的（假设是从小到大排列的），那就意味着最小的元素一个一个往前移！希尔排序的主要特点：首先将排序区间按照一定的区间划分为若干个小区间，对每个小区间进行插入排序，然后缩小区间直到为1，再次进行插入排序。1和3可以合为1类。一般来说，每次划分排序之后，整体区间的有序度都会增加，也就是每次区间变窄之后，我们重新排序的有序度会整体提升。这句话需要仔细理解。先用一张图来表达一下：首先，我们要排序的数据集是9,2,12,28,44,56,7,8,14,3,15,1，我们取步长区间为数据第一次Length/2，然后再次除以2，直到为1。可以看出，最小元素的位置很快就确定了，排在了最前面。同时我们最后的排序也是在高度有序的基础上进行的。代码实现functionsort(arr){letl=arr.length;for(letstep=l>>1;step>0;step>>=1){for(leti=step;i=0&&target<=arr[j];j-=step){/***移动数据，注意需要加上Steplength，这个地方不太好理解，大家可以想象it，我们不是顺序比较*想象分离比较同步长度的下标元素*/arr[j+step]=arr[j]}arr[j+step]=target}}}进行分析1.是希尔排序就地算法？是2.希尔排序是稳定算法吗？其实不太容易想到，因为我们是划分区间进行排序的，所以很可能会导致相同元素位置的相对顺序发生变化。举个最简单的例子7,2(a),2(b),1开始7,2(b)排序，2(a),1排序第一个结果2(b),1,7,2(a)的可以发现两个2的相对变化。3.希尔排序的时间复杂度是多少？最佳：O(nlogn)。最差：O(nlogn)。平均：O(nlogn)。由于时间紧迫，可能有些地方会有错别字，代码实现可能不是最简单最好的。请多多包涵。下一篇文章将介绍一些复杂度为nlogn的排序算法。大家来吧！
