跳到主要内容

插入排序

2024年04月03日
柏拉文
越努力，越幸运

一、认识​

插入排序英文称为 Insert Sort。

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。

如果是数组的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

特点:

  • 稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。插入排序的过程不会破坏原有数组中相同关键字的相对次序，所以插入排序是一种稳定的排序算法。
  • 原地排序: 原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
  • 排序方式: In-place (不占用额外内存，只占用常数内存)
  • 时间复杂度: O(n2n^{2}) [n 代表数据规模及数据量大小]
  • 空间复杂度: O(1)

扩展:

  • 排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

二、思想​

  • 默认 nums[0] 为有序序列
  • 从 nums[1] 开始当作插入元素，依次与有序序列中的元素进行比较，如果有序序列中的元素比插入元素大有序序列中的元素就不断的向后移动
  • 先插入元素找到合适的插入位置后，插入

三、实现​

function sortArray(nums){
    for(let i=1;i<nums.length;i++){
    let value=nums[i];
    let index=i-1;
    while(index>=0&&value<nums[index]){
        nums[index+1]=nums[index];
        index--;
    }
        nums[index+1]=value;
    }
    return nums;
}

性能分析:

  • 时间复杂度为 O(n^2)
  • 空间复杂度为 O(1)