直接插入排序的步骤
1. 从前面的有序子表中查找出待插入元素应该被插入的位置
2. 给插入位置腾空间
3. 将待插入元素复制到表中的插入位置。
直接插入排序:边比较边移动;
折半插入排序
先折半查找出元素的待插入位置,然后统一地移动待插入位置之后的所有元素。
基本思想
1. 将待排序序列的第一个元素看做有个有序序列,把第二个元素到最后一个元素看做未排序序列。
2. 从头(第二个元素)到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置;在查找元素的适当位置时,采用折半查找的方式。也就是说,折半查找的是有序序列中合适的位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)。
演示
只展示一个效果,下次再补充后面的循环;
代码展示
let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
/**
*
* @param {*} ary 数组
* @param {*} length 长度
*/
function halfSort(ary, length) {
for (let i = 1; i < length; i++) {
// 从第二个元素开始扫描
let temp = ary[i];
let low = 0,
high = i - 1; // 标记有序队列
// 折半查找有序子列
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (ary[mid] > temp) {
high = mid - 1;
} else {
low = mid + 1;
}
}
// 统一移动位置,从后向前移动,腾出位置
for (let j = i - 1; j >= high + 1; j--) {
ary[j + 1] = ary[j];
}
ary[high + 1] = temp;
console.log("ary", JSON.stringify(ary));
}
}
halfSort(ary, ary.length);
结果:
ary [3,8,1,9,4,5,6,2,7]
ary [1,3,8,9,4,5,6,2,7]
ary [1,3,8,9,4,5,6,2,7]
ary [1,3,4,8,9,5,6,2,7]
ary [1,3,4,5,8,9,6,2,7]
ary [1,3,4,5,6,8,9,2,7]
ary [1,2,3,4,5,6,8,9,7]
ary [1,2,3,4,5,6,7,8,9]
性能分析
时间复杂度 | 空间复杂度 |
最好的时间复杂度O(nlogn);最坏时间复杂度O(n^2) | O(1) |
平均时间复杂度O(n^2) |
总结:
1. 折半插入排序仅仅减少了比较元素的次数,约为O(nlogn);
2. 比较次数与待排序表的初始状态无关,仅仅取决于表中的元素个数n
3. 元素的移动次数并未改变,它依赖与待排序表的初始状态。
4. 折半插入排序是一种稳定的排序方法
5. 只适用于顺序表,不适用链表