第三，插入排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n)，当数据已经是正序时。
最差情况：T(n) = O(n2)，当数据是反序时。
平均情况：T(n) = O(n2)。
动画
二、拆半插入
插入排序也有一种优化算法，叫做拆半插入。
思想
折半插入排序是直接插入排序的升级版，鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点, 只需比较它们的中间值与待插入元素的大小即可。
步骤
取 0 ~ i-1 的中间点 ( m = (i-1)>>1 )，array[i] 与 array[m] 进行比较，若 array[i] < array[m]，则说明待插入的元素 array[i] 应该处于数组的 0 ~ m 索引之间；反之，则说明它应该处于数组的 m ~ i-1 索引之间。
重复步骤 1，每次缩小一半的查找范围，直至找到插入的位置。
将数组中插入位置之后的元素全部后移一位。
在指定位置插入第 i 个元素。
注：x>>1 是位运算中的右移运算，表示右移一位，等同于 x 除以 2 再取整，即 x>>1 == Math.floor(x/2) 。
// 折半插入排序 const binaryInsertionSort = array => { const len = array.length; if (len <= 1) return; let current, i, j, low, high, m; for (i = 1; i < len; i++) { low = 0; high = i - 1; current = array[i]; while (low <= high) { //步骤 1 & 2 : 折半查找 m = (low + high) >> 1; // 注: x>>1 是位运算中的右移运算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) . if (array[i] >= array[m]) { //值相同时, 切换到高半区，保证稳定性 low = m + 1; //插入点在高半区 } else { high = m - 1; //插入点在低半区 } } for (j = i; j > low; j--) { //步骤 3: 插入位置之后的元素全部后移一位 array[j] = array[j - 1]; console.log('array2 :', JSON.parse(JSON.stringify(array))); } array[low] = current; //步骤 4: 插入该元素 } console.log('array2 :', JSON.parse(JSON.stringify(array))); return array; };测试
const array2 = [5, 4, 3, 2, 1]; console.log('原始 array2:', array2); binaryInsertionSort(array2); // 原始 array2: [5, 4, 3, 2, 1] // array2 : [5, 5, 3, 2, 1] // array2 : [4, 5, 5, 2, 1] // array2 : [4, 4, 5, 2, 1] // array2 : [3, 4, 5, 5, 1] // array2 : [3, 4, 4, 5, 1] // array2 : [3, 3, 4, 5, 1] // array2 : [2, 3, 4, 5, 5] // array2 : [2, 3, 4, 4, 5] // array2 : [2, 3, 3, 4, 5] // array2 : [2, 2, 3, 4, 5] // array2 : [1, 2, 3, 4, 5]注意：和直接插入排序类似，折半插入排序每次交换的是相邻的且值为不同的元素，它并不会改变值相同的元素之间的顺序，因此它是稳定的。
三、希尔排序
希尔排序是一个平均时间复杂度为 O(nlogn) 的算法，会在下一个章节和 归并排序、快速排序、堆排序 一起讲，本文就不展开了。
5. 选择排序思路
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
实现
const selectionSort = array => { const len = array.length; let minIndex, temp; for (let i = 0; i < len - 1; i++) { minIndex = i; for (let j = i + 1; j < len; j++) { if (array[j] < array[minIndex]) { // 寻找最小的数 minIndex = j; // 将最小数的索引保存 } } temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; console.log('array: ', array); } return array; };测试
// 测试 const array = [5, 4, 3, 2, 1]; console.log('原始array:', array); selectionSort(array); // 原始 array: [5, 4, 3, 2, 1] // array: [1, 4, 3, 2, 5] // array: [1, 2, 3, 4, 5] // array: [1, 2, 3, 4, 5] // array: [1, 2, 3, 4, 5]分析
第一，选择排序是原地排序算法吗 ？
选择排序空间复杂度为 O(1)，是一种原地排序算法。
第二，选择排序是稳定的排序算法吗 ？
选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。所以，选择排序是一种不稳定的排序算法。