插入排序是一种排序算法，是基于就地比较的算法。
该算法通过将元素放置在已排序子数组中的位置进行工作，即在元素之前的子数组是已排序子数组。
步骤1-从1循环到n-1并执行-
步骤2.1-选择位置i处的元素array [i]。
步骤2.2-将元素插入已排序的子数组array [0]中的位置到arr [i]。
让我们以一个例子来了解算法
数组= [34、7、12、90、51]
对于i = 1，arr [1] = 7，将其放置在子数组arr [0]-arr [1]中。
[7, 34, 12, 90, 51]
对于i = 2，arr [2] = 12，放置在子数组arr [0]-arr [2]中。
[7, 12, 34, 90, 51]
对于i = 3，arr [3] = 90，放在子数组arr [0]-arr [3]中。
[7, 12, 34, 90, 51]
对于i = 4，arr [4] = 51，放在子数组arr [0]-arr [4]中。
[7, 12, 34, 54, 90]
在这里，我们将看到递归插入排序的工作原理。它以相反的方式工作，即recursiveInsertionSort()与当前迭代相比，我们将递归调用该函数以对n-1元素数组进行排序。然后在该函数将返回的排序数组中，我们将在排序数组中的位置插入第n个元素。
递归插入排序程序-
#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
if (n <= 1)
return;
recursiveInsertionSort( arr, n-1 );
int nth = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > nth){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = nth;
}
int main(){
int array[] = {34, 7, 12, 90, 51};
int n = sizeof(array)/sizeof(array[0]);
printf("Unsorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
recursiveInsertionSort(array, n);
printf("\nSorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
return 0;
}输出结果
Unsorted Array: 34 7 12 90 51 Sorted Array: 7 12 34 51 90