数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究递归插入排序的 C 程序
插入排序是一种排序算法，它是一种基于比较的原地算法。
该算法通过将元素放在已排序子数组中的位置来工作，即元素之前、已排序的子数组。
算法
第 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("
Sorted 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
更新于: 2020 年 7 月 17 日
3K+ 浏览
广告