1. 从第 2 个元素开始，依次向前比较，比当前元素大的依次往后移
2. 直到找到比当前元素小的，或者 prevIndex < 0 ，将当前元素插入到该元素后面

3. 时间复杂度是 O(n^2)，空间复杂度 O(1)

   代码核心逻辑

4. 一层 for 循环，一层 while 循环

5. 第 1 层 for 循环代表当前要比较的元素
6. 第 2 层 while 循环，查找比当前元素大的元素，大就往后移，小就退出循环

7. 将当前元素插入到查找到的元素后面

   代码

   ```javascript function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const current = arr[i]; // 暂存当前元素 let prevIndex = i - 1; // 前面元素下标

   while(prevIndex >= 0 && arr[prevIndex] > current) { arr[prevIndex + 1] = arr[prevIndex]; // 后移 prevIndex—; }

   arr[prevIndex + 1] = current; // 插入到下标是 prevIndex 的元素后面 }

   return arr; }

const arr = [3, 2, 9, 1, 4, 8, 5, 7, 0, 6];

console.time(); console.log(insertionSort(arr)); console.timeEnd();

// default: 0.4111328125 ms ```