插入排序

基本思想

将数组分为已排序和未排序两部分，将未排序的元素放到已排序数组中正确的位置的。

具体操作：从index=1开始遍历一趟数组，将当前遍历元素的前面视为有序数组，将当前元素从有序数组从后往前比较 如果比他大，就说明当前index的位置就是插入的位置 如果比他小，就说当前index的值插入位置在前面。把当前有序数组往后移，为接下来的循环空出位置。

一般实现

function insertSort(nums){
       for(let i=1;i<nums.length;i++){
           let currentValue=nums[i];
           let j=i-1;
           //将当前值插入到已排序部分的正确位置
           while(j>=0 && nums[j]>currentValue){
               nums[j+1]=nums[j];//为后续找到的位置空出来插入
               j--;
           }
           //找到插入的位置，就是就是先前空出来的位置
           nums[j+1]=currentValue;
       }
       return nums;
   }
   
   const result = insertSort(nums);
   console.log(result); // 输出排序后的数组

递归实现

function insert(sortedArr, value) {
     const arr = [...sortedArr]; // 创建一个副本，保证不修改原数组
     let i = arr.length - 1;
     
     // 找到插入位置
     while (i >= 0 && arr[i] > value) {
       i--;
     }
     
     // 使用 slice 和扩展语法来插入元素，生成新数组
     return [...arr.slice(0, i + 1), value, ...arr.slice(i + 1)];
   }
   
   /**
    * 纯函数式的递归插入排序
    * @param {number[]} nums - 待排序的数组。
    * @returns {number[]} - 一个全新的、排好序的数组。
    */
   function insertSortPure(nums) {
     // 基本情况：如果数组为空或只有一个元素，它已经是有序的。
     if (nums.length <= 1) {
       return [...nums]; // 返回副本以保证纯粹性
     }
   
     // 递归步骤：
     // 1. 将数组分为“最后一个元素”和“前面的所有元素”
     const last = nums[nums.length - 1];
     const rest = nums.slice(0, nums.length - 1); // .slice() 返回一个新数组
   
     // 2. 递归地对“前面的所有元素”进行排序
     const sortedRest = insertSortPure(rest);
   
     // 3. 将“最后一个元素”插入到已排序的前半部分中
     return insert(sortedRest, last);
   }

reference