直接插入排序算法详解
直接插入排序（Straight Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为最新元素提供插入空间。
直接插入排序的步骤
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤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;
}
};
原文地址：https://blog.csdn.net/qq_62784063/article/details/140578370
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！