带你读《图解算法小抄》十四、排序（5）https://developer.aliyun.com/article/1348145?groupCode=tech_library
6）算法优化改进
改进方法① - 二分插入排序
二分插入排序是对直接插入排序的改进，使用二分查找来找到插入位置，从而减少比较的次数。
改进代码：
// 二分插入排序function binaryInsertionSort(arr) { const len = arr.length; for (let i = 1; i < len; i++) { let current = arr[i]; let left = 0; let right = i - 1; while (left <= right) { let middle = Math.floor((left + right) / 2); if (arr[middle] > current) { right = middle - 1; } else { left = middle + 1; } } for (let j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } arr[left] = current; }}
改进方法② - 希尔排序
希尔排序是对插入排序的进一步改进，通过将数组分成多个子序列进行插入排序，逐渐缩小子序列的间隔，最终实现全局的排序。
7）复杂度
名称 |
最佳情况 |
平均情况 |
最坏情况 |
内存 |
稳定性 |
备注 |
插入排序 |
n |
n2 |
n2 |
1 |
是 |
|
8）参考资料
维基百科
4.归并排序
归并排序（Merge Sort）是一种高效的通用比较排序算法。大多数实现都产生稳定排序，这意味着算法会保留排序输出中相等元素的输入顺序。归并排序是一种分治算法，由约翰·冯·诺伊曼（John von Neumann）于1945年发明。
下图是归并排序的示例。首先将列表划分为最小单位（1个元素），然后将每个元素与相邻的列表进行比较，以便排序和合并相邻的列表。最后，所有元素都被排序和合并。
下图是用于对包含7个整数值的数组进行排序的递归归并排序算法。这些步骤是人类为了模拟归并排序而采取的操作（自顶向下）。
带你读《图解算法小抄》十四、排序（7）https://developer.aliyun.com/article/1348143?groupCode=tech_library
