插入排序算法 ,遞歸實現
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 ith iteration. Feel free to ask your doubts.
此輸出顯示每次第 i 次迭代后的數組。 隨時提出您的疑問。
翻譯自: https://www.includehelp.com/c-programs/implement-recursive-insertion-sort.aspx
插入排序算法 ,遞歸實現
