带你读《图解算法小抄》十四、排序(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