直接插入排序算法详解

直接插入排序（Straight Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为最新元素提供插入空间。

直接插入排序的步骤

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

直接插入排序的性能

• 时间复杂度：

  • 最好情况（输入数组已经是排序好的）：O(n)，其中n是数组的长度。
  • 最坏情况（输入数组是逆序的）：O(n^2)。
  • 平均情况：O(n^2)。

• 空间复杂度：O(1)，因为它是一种原地排序算法，只需要常量级别的额外空间。

• 稳定性：稳定排序。如果两个相等的元素在排序前的相对顺序和排序后的相对顺序相同，则认为排序是稳定的。在直接插入排序中，如果两个元素相等，则后出现的元素不会移动到先出现的元素之前，因此它是稳定的。

实际应用

尽管直接插入排序在大数据集上效率不高，但由于其实现简单，且在小规模数据或基本有序的数据集上性能良好，因此在某些情况下仍然被使用。此外，它也是其他更复杂排序算法（如希尔排序）的基础。

模板代码：

class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n=nums.size();for(int i=1;i<n;i++){                       //对nums[0...n-1]进行直接插入排序if(nums[i-1] > nums[i]){                //需要插入到前面已经排好序的子表中int j,temp=nums[i];                 //temp暂存待插入元素for(j=i-1;j>=0 && nums[j]>temp;j--) //将大于temp的元素全部向后移以为，给nums[i]腾出空间nums[j+1]=nums[j];nums[j+1]=temp;}}return nums;}
};