首页 > 后端开发 > C++ > 递归插入排序的C程序

递归插入排序的C程序

WBOY
发布: 2023-09-20 14:37:09
转载
894 人浏览过

递归插入排序的C程序

插入排序是一种排序算法,它是一种基于就地比较的算法。

该算法的工作原理是将元素放置在已排序子数组中的位置,即元素之前的子数组是排序子数组。

算法

Step1 - 从 1 到 n-1 循环并执行 -

Step2 .1 - 选择位置 i 处的元素,array[i]。

Step2.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("</p><p>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
登录后复制

以上是递归插入排序的C程序的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板