C++ 程序递归插入排序

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

插入排序算法

  • int arr[5]= { 5,4,2,1,3 };

  • 内部 i, j ;

  • 从索引 j=i+1 遍历到 j<array size

  • 对于每个元素 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

输出 - 排序数组:1 2 3 4 5 7

说明 -

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 };

输出 - 排序数组:1 2 2 3 3

说明-

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(int arr[], int len) 获取数组及其长度,并使用冒泡排序对数组进行递归排序。

  • 取一个可变温度。

  • 如果数组长度为 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

以上是 C++ 程序递归插入排序 的全部内容, 来源链接: utcz.com/z/355849.html

回到顶部