邵阳做网站哪家好,保健品网站建设流程,起飞页做网站,wordpress图片间距直接插入排序#xff08;Straight Insertion Sort#xff09;是一种简单直观的排序算法。它的工作原理是通过构建有序序列#xff0c;对于未排序数据#xff0c;在已排序序列中从后向前扫描#xff0c;找到相应位置并插入。插入排序在实现上#xff0c;通常采用in-place排…直接插入排序Straight Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间的排序因而在从后向前扫描过程中找到排序位置后需要将已排序元素逐步向后挪位为最新元素提供插入空间。
直接插入排序的步骤
从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已经排序的元素序列中从后向前扫描。如果该元素已排序大于新元素将该元素移到下一位置。重复步骤3直到找到已排序的元素小于或等于新元素的位置。将新元素插入到该位置后。重复步骤2~5。
直接插入排序的性能 时间复杂度 最好情况输入数组已经是排序好的O(n)其中n是数组的长度。最坏情况输入数组是逆序的O(n^2)。平均情况O(n^2)。 空间复杂度O(1)因为它是一种原地排序算法只需要常量级别的额外空间。 稳定性稳定排序。如果两个相等的元素在排序前的相对顺序和排序后的相对顺序相同则认为排序是稳定的。在直接插入排序中如果两个元素相等则后出现的元素不会移动到先出现的元素之前因此它是稳定的。
实际应用
尽管直接插入排序在大数据集上效率不高但由于其实现简单且在小规模数据或基本有序的数据集上性能良好因此在某些情况下仍然被使用。此外它也是其他更复杂排序算法如希尔排序的基础。
模板代码
class Solution {
public:vectorint sortArray(vectorint nums) {int nnums.size();for(int i1;in;i){ //对nums[0...n-1]进行直接插入排序if(nums[i-1] nums[i]){ //需要插入到前面已经排好序的子表中int j,tempnums[i]; //temp暂存待插入元素for(ji-1;j0 nums[j]temp;j--) //将大于temp的元素全部向后移以为给nums[i]腾出空间nums[j1]nums[j];nums[j1]temp;}}return nums;}
};
