C++ 程序递归插入排序

插入排序是一种排序算法，用于通过插入诸如一副卡片之类的元素来对数据进行排序。所有元素从左到右排列，然后将第一个元素视为已经排序，将其余元素插入左侧的排序列表。每个元素与左列表中的每个元素进行比较，直到它被插入到正确的位置。

插入排序算法

intarr[5]={5,4,2,1,3};

内部i,j;

从索引j=i+1遍历到j<arraysize

对于每个元素arr[j]将其与列表arr[0到i]中的元素进行比较，直到找到满足arr[i]<arr[j]和arr[i+1]>=arr[j]的元素。

将arr[j]放在列表中并将所有较大的元素向右移动一个位置。

结尾

递归插入排序

如果数组长度为1，则返回。

将索引0处的元素递归地排序到数组大小1

插入排序数组中的最后一个元素

例子

输入 -Arr[]={5,7,2,3,1,4};长度=6

输出 -排序数组：123457

说明 -

5 7 2 3 1 4 → 5 already sorted 5 7 2 3 1 4 → 7 at correct place 2 5 7 3 1 4 → 2 compared with 5,7 and inserted 2 3 5 7 1 4 → 3 compared with 5,7 and inserted 1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted 1 2 3 4 5 7 → 4 compared with 5,7 and inserted

输入 -Arr[]={1,2,3,3,2};

输出 -排序数组：12233

说明-

1, 2, 3, 3, 2 → 1 already sorted 1, 2, 3, 3, 2 → 2 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted

下面程序中使用的方法如下

在冒泡排序的递归方法中，基本情况是数组长度=1。否则使用单个for循环遍历数组并相应地交换元素。

将输入数组Arr[]和长度作为其中的元素数。

函数recurbublSort(intarr[],intlen)获取数组及其长度，并使用冒泡排序对数组进行递归排序。

取一个可变温度。

如果数组长度为1，则返回void。

否则使用单个for循环遍历数组，并为每个元素arr[i]>arr[i+1]交换这些元素。

设置temp=arr[i]、arr[i]=arr[i+1]和arr[i+1]=temp。

现在将长度减1，因为前一个循环将最大元素放在最后一个位置。

递归调用recurbublSort(arr,len).

在所有调用结束时，当len变为1时，我们将退出递归并对数组进行排序。

在main中打印排序后的数组。

示例

#include <bits/stdc++.h> using namespace std; void recurbublSort(int arr[], int len){ int temp; if (len == 1){ return; } for (int i=0; i<len-1; i++){ if (arr[i] > arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; } } len=len-1; recurbublSort(arr, len); } int main(){ int Arr[] = {21, 34, 20, 31, 78, 43, 66}; int length = sizeof(Arr)/sizeof(Arr[0]); recurbublSort(Arr, length); cout<<"排序数组： "; for(int i=0;i<length;i++){ cout<<Arr[i]<<" "; } return 0; }输出结果

如果我们运行上面的代码，它将生成以下输出

排序数组： 20 21 31 34 43 66 78