直接插入排序（Straight Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，找到排序位置后，需要將已排序元素逐步向后挪位，為最新元素提供插入空間。

直接插入排序的步驟

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序。
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描。
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置。
4. 重復步驟3，直到找到已排序的元素小于或等于新元素的位置。
5. 將新元素插入到該位置后。
6. 重復步驟2~5。

直接插入排序的性能

• 時間復雜度：

  • 最好情況（輸入數(shù)組已經(jīng)是排序好的）：O(n)，其中n是數(shù)組的長度。
  • 最壞情況（輸入數(shù)組是逆序的）：O(n^2)。
  • 平均情況：O(n^2)。

• 空間復雜度：O(1)，因為它是一種原地排序算法，只需要常量級別的額外空間。

• 穩(wěn)定性：穩(wěn)定排序。如果兩個相等的元素在排序前的相對順序和排序后的相對順序相同，則認為排序是穩(wěn)定的。在直接插入排序中，如果兩個元素相等，則后出現(xiàn)的元素不會移動到先出現(xiàn)的元素之前，因此它是穩(wěn)定的。

實際應用

盡管直接插入排序在大數(shù)據(jù)集上效率不高，但由于其實現(xiàn)簡單，且在小規(guī)模數(shù)據(jù)或基本有序的數(shù)據(jù)集上性能良好，因此在某些情況下仍然被使用。此外，它也是其他更復雜排序算法（如希爾排序）的基礎。

模板代碼：

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]){                //需要插入到前面已經(jīng)排好序的子表中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;}
};