插入排序算法 ,递归实现

The only difference between Insertion sort and Recursive Insertion Sort is that in the Recursive method, we start from placing the last element in its correct position in the sorted array instead of starting from the first.

插入排序和递归插入排序之间的唯一区别是，在递归方法中，我们从将最后一个元素放置在已排序数组中的正确位置开始，而不是从第一个元素开始。

Here, I will only be showing the C implementation of the sort as I have explained the basic theory in my previous article.

在这里，我将仅按照我在上一篇文章中解释的基本理论来说明该类的C实现。

Recursive Insertion Sort Implementation:

递归插入排序实现：

#include <stdio.h>

void rec_insertion(int arr[], int n)
{
    // When the elements are all over
    if (n <= 1)
        return;

    // sorting n-1 elements
    rec_insertion(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

    while (j >= 0 && last < arr[j]) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;

    printf("\nAfter performing Insertion sort:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

int main()
{
    int arr[] = { 10, 14, 3, 8, 5, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);

    rec_insertion(arr, n);

    return 0;
}

Output:

输出：

After performing Insertion sort:
10 14
After performing Insertion sort:
3 10 14
After performing Insertion sort:
3 8 10 14
After performing Insertion sort:
3 5 8 10 14
After performing Insertion sort:
3 5 8 10 12 14

This output shows the array after each i^th iteration. Feel free to ask your doubts.

此输出显示每次^第 i ^次迭代后的数组。 随时提出您的疑问。

翻译自: https://www.includehelp.com/c-programs/implement-recursive-insertion-sort.aspx

插入排序算法 ,递归实现