1959年由Shell发明，第一个突破O(n^2^)的排序算法是简单插入排序的改进版。它与插入排序的不同之处在于它首先比较距离较远的元素。插入排序插入排序的工作原理是建立一个有序的序列。对于未排序的数据，在已排序的序列中从后往前扫描，找到对应位置插入代码：functioninsertionSort(arr){letn=arr.length;letpreIndex,current;for(leti=1;i=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];preIndex--;}arr[preIndex+1]=current;}returnarr;}插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置插入，并保证已排序区间数据始终在为了。重复这个过程，直到未排序区间内的元素为空，算法结束。复杂度分析：时间复杂度：O(n^2^)空间复杂度：O(1)希尔排序回顾一下上面的插入排序：经过第一次插入排序，我们得到的有效序列长度为2第二次经过插入排序，长度为我们得到的有效序列是3...直到序列被排序。那么，如果序列够乱，时间复杂度就是O(n^2^)希尔排序是如何优化的呢？希尔排序也叫收缩增量排序，就是对系列进行分组（分组中连续使用插入排序），直到从宏观上看是有序的，最后插入排序很容易（不需要多次移位或交换）.组数称为增量。显然，增量是不断递减的（直到增量为1）。那我们怎么分组呢？通常：如果一个数组有8个元素，我们第一遍的增量是4，第二遍的增量是2，第三遍的增量是1。如果一个序列有18个元素，我们第一次递增9，第二次递增4，第三递增2，第四递增1。显然我们可以用一个序列来表示递增：n/2,(n/2)/2,...,1，每次递增/2例如：letarr=[4,1,5,8,7,3]排序前：把数组看成三组（Math.floor(arr.length/2))，分别是：[4,1],[5,8],[7,3]第一次排序：三组数据分别进行插入排序，所以我们三个数组得到的结果是：[1,4],[5,8],[3,7]这时候数组是这样的：[1,4,5,8,3,7]第二次排序：递减递减，上面increment为3，此时increment应该为1，所以把[1,4,5,8,3,7]当成一个数组（从宏上面排序），插入排序，直到有序码实现：functionshellSort(arr){letn=arr.length;for(letgap=Math.floor(n/2);gap>0;gap=Math.floor(gap/2)){for(leti=gap;i=0&¤t
