插入排序
插入排序
基本概念
插入排序，对应的英语是 Insertion Sort，其核心思想类似于整理扑克牌：在手中已经排好序的牌堆中，逐张拿出未排序的牌，找到合适的位置插入进去，直到所有牌都有序为止。
下面是插入排序的工作流程：
-
分区概念：将数组分为两个部分：已排序区间 和 未排序区间。初始时，默认第一个元素为已排序区间，其余元素为未排序区间。
-
逐个插入：从未排序区间中取出第一个元素，依次与已排序区间的元素进行比较，将其插入到合适的位置，使得已排序区间依然保持有序。
-
移动元素：当新元素小于已排序区间中的某个元素时，需要将该元素及其后续元素依次向后移动，为新元素腾出插入位置。
-
重复操作：重复以上过程，直到未排序区间为空，整个数组变成有序序列。
代码实现
function insertionSort(arr){
// 从第二个元素开始，到最后一个元素
// 因为会假设第一个元素已经排好顺序了
for(int i = 1; i < arr.length; i++){
// 取出每一个要插入的元素
let current = arr[i];
// 要和已排序区间里面的元素进行比较，找到正确的插入位置
// j 一开始是已排序区间的最后一个元素
let j = i - 1;
// 这个循环负责将已排序区间的元素往后面移动
while(j >= 0 && arr[j] > current){
arr[j+1] = arr[j];
j--;
}
// 跳出 while 循环的时候，说明当前元素已经找到插入的位置了
arr[j+1] = current;
}
}
const arr = [5, 3, 8, 4, 2];
insertionSort(arr);
console.log(arr);
- 外层 for 循环：从第二个元素开始，将每个元素看作是待插入的元素。
- 内层 while 循环：将当前待插入的元素和已排序区间的每一个元素逐一比较，如果当前待插入元素小于已排序元素，直接将已排序元素往后移动，直到找到正确的插入位置。
复杂度
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1)
稳定性
因为插入排序，待插入的元素只有在大于前一个数的时候，已排序区域的元素才会往后移动，值相等的话，是插入到有序数列中相同数的后面的。因此，插入排序是一种 稳定 排序。
我的实现
function sort(arr) {
// 此处我的想法是定义一个已排序区域下标，外层for循环去循环未排序部分，内层for循环去从第一个元素开始
// 循环已排序部分，然后挨个对比交换，这样的写法相较于老师的写法效率要低，因为已排序部分本来是顺序的，
// 我这样写会多循环很多次
let index = 0
for(let i = index + 1; i < arr.length; i++) {
for(let j = 0; j <= index; j++) {
if(arr[j] < arr[i]) {
let mid = arr[i]
arr[i] = arr[j]
arr[j] = mid
}
}
index ++
}
return arr
}
function tSort(arr) {
for(let i = 1; i < arr.length; i++) {
let j = i - 1
let tar = arr[i]
while(arr[j] < tar && j >= 0) {
arr[j + 1] = arr[j]
j--
}
arr[j+ 1] = tar
}
return arr
}
console.log(tSort([7,2,5,2,1,7,6,2,0,67,3]))
-EOF-