一、算法原理

插入排序是一种简单直观的排序算法，它的工作原理是将未排序数据插入到已排序序列的合适位置。具体来说，插入排序将数组分为已排序和未排序两部分，初始时已排序部分只有数组的第一个元素，然后依次从未排序部分取出元素，将其插入到已排序部分的合适位置，直到整个数组都被排序。

二、详细代码

#include<iostream>
using namespace std;int InsertSort(int arr[], int size)
{int x, i;for( int j = 1; j < size; j++){x = arr[j];i = j - 1;while( i >= 0 && x < arr[i]){arr[i+1] = arr[i];i = i - 1;}arr[i+1] = x;}for(int s = 0; s < size; s++){cout<<arr[s]; }cout<<endl;
}int main()
{int size;std::cout<<"Enter size:";std::cin>>size;int* arr =new int[size];for(int i = 0;i<size;i++){cout<<"arr element:";cin>>arr[i]; }
InsertSort(arr,size);
delete[] arr;
return 0;}

三、详细解释

• 排序过程：

  1. 外层循环：for( int j = 1; j < size; j++)，从数组的第二个元素开始（索引为 1），依次将未排序部分的元素插入到已排序部分。
  2. 保存当前元素：x = arr[j];，将当前要插入的元素保存到变量 x 中。
  3. 内层循环：while( i >= 0 && x < arr[i])，从已排序部分的最后一个元素开始，向前比较，如果当前元素 x 小于已排序部分的元素 arr[i]，则将 arr[i] 向后移动一位，即 arr[i+1] = arr[i];，并将 i 减 1。
  4. 插入元素：当找到合适的位置后，将当前元素 x 插入到该位置，即 arr[i+1] = x;。

• 输出排序结果：

  • 使用 for 循环遍历数组，并使用 cout 输出每个元素，最后换行。

复杂度分析

• 时间复杂度：插入排序的平均时间复杂度和最坏时间复杂度都是O(n2) ，其中n 是数组的大小。在最好情况下，即数组已经有序时，时间复杂度为O(n) 。
• 空间复杂度：插入排序只需要常数级的额外空间，因此空间复杂度为 O(1)。