直接插入排序

介绍

插入排序 这是十大排序算法里的基础排序，也是我们平常人能够清晰理解的一种排序方式。

插入排序的原理就是：将当前的数据分成两组，一组是有序状态，一组是无序状态（待插入），每次从无序状态的数组里，取出一个院苏，然后与有序状态下的数组的元素进行比对，找到属于自己合适的位置，并将其插入到有序数状态的组中即可。这样循环进行，无序状态下的数组元素依次减少直至为0，有序状态下的数组依次增多直至为最大长度。

下面是动态图的一个演示

步骤

插入排序 的步骤：

• 将数组的第一个元素看成有序状态的数组，第二个元素到最后一个元素为无序状态的数组。
• 从第二个元素开始，依次往后取出，与有序状态下的数组元素进行比对，并放置在有序状态的数组里。

题目

1. 排序数组-912

   给你一个整数数组 nums，请你将该数组升序排列

2. 对链表进行插入排序-147

   对 链表 进行插入排序。插入排序的动画演示如下。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中

代码

• 排序数组 912题

      const sortArray = (nums) => {
        const numsLength = nums.length
  
        for (let i = 1; i < numsLength; i++) {
            // 当前无序数组下的第一个元素，也就是将要插入的元素
            let currentDisorderFirstEle = nums[i]
  
            // 当前的 j 是有序数组下的 最后一个元素
            let j = i - 1
  
            // 1.从后往前 进行遍历有序数组里的元素，最后一个元素是j
            // 2.判断 要插入的元素 是否小于 num[j]
            while (j >= 0 && currentDisorderFirstEle < nums[j]) {
                nums[j + 1] = nums[j]
                j--
            }
  
            // 最后j的位置+1 就是这个要插入的元素 在有序数组里的位置
            nums[j + 1] = currentDisorderFirstEle
        }
        return nums
      }
  

• 对链表进行插入排序 147题

      const insertionSortList = (head) => {
        if (head === null) return head
  
        // 有序链表的无头指针，它的next指向head
        const headLess = new ListNode(0)
        headLess.next = head
  
        // 有序链表的第一个元素
        let orderLinkedEndEle = head
  
        // 无序链表的第一个元素
        let disorderLinkedFirstEle = head.next
  
        while (disorderLinkedFirstEle !== null) {
          // 判断有序列表的最后一个元素 与 待插入的 disorderLinkedFirstEle 进行比较
          if (orderLinkedEndEle.val > disorderLinkedFirstEle.val) {
            // 将无头指针进行赋值,latestLocation 最新的位置
            let latestLocation = headLess
  
            // 进行比较，第一次比较的意思就是 latestLocation.next.val = head.val
            while (latestLocation.next.val <= disorderLinkedFirstEle.val) {
              // 如果小于 待插入的元素，那就一直找，找到刚大于 待插入的元素 的 位置
              latestLocation = latestLocation.next
            }
  
            // 结束循环的话，我们就找到了，要 插入元素 disorderLinkedFirstEle.next 在有序链表的位置 就是 latestLocation.next
            // 而且，我们需要将 有序列表的最后一个元素.next = 插入元素.next,防止找不到
            // latestLocation  --> disorderLinkedFirstEle --> latestLocation.next
  
            orderLinkedEndEle.next = disorderLinkedFirstEle.next
  
            disorderLinkedFirstEle.next = latestLocation.next
  
            latestLocation.next = disorderLinkedFirstEle
          } else {
            orderLinkedEndEle = orderLinkedEndEle.next
          }
  
          // 重新更新无序列表的第一个元素
          disorderLinkedFirstEle = orderLinkedEndEle.next
        }
        return headLess.next
      }