C++中的递归选择排序
选择排序是一种排序算法,用于通过从头开始迭代数组并将每个元素替换为列表中的最小元素来对数据进行排序。当我们向前移动时,左侧数组已排序,右侧数组未排序。每次移动都通过交换将下一个最小的位置放置到索引的当前位置。
选择排序算法
intarr[5]={5,4,2,1,3};
内部i,j;
从索引i=0到i<arraysize-1遍历
从索引j=i+1遍历到数组大小-1
找到最小的并存储它的index.pos
使用arr[i]交换找到的索引pos处的元素
结尾
递归选择排序
查找最小元素的索引
如果找到的最小元素索引等于数组大小,则返回。
否则用最小元素交换当前元素
对数组的其余部分递归执行上述步骤,不包括已排序的元素
例子
输入 -Arr[]={5,7,2,3,1,4};长度=6
输出 -排序数组:123457
说明-
First Pass :- 5 7 2 3 1 4 → swap → 1 2 7 3 5 4 1 2 7 3 5 4 → no swap 1 2 7 3 5 4 → swap → 1 2 3 7 5 4 1 2 3 7 5 4 → swap → 1 2 3 4 5 7 1 2 3 4 5 7 → no swap
输入 -Arr[]={1,2,3,3,2};
输出 -排序数组:12233
说明-
1 2 3 3 2 → no swap 1 2 3 2 3 → no swap 1 2 3 2 3 → swap → 1 2 2 3 3 1 2 2 3 3 → no swap
下面程序中使用的方法如下
在选择排序的递归方法中,基本情况是最小索引=数组大小-1。否则从与当前索引交换的数组中找到最小值并递归排序正确的未排序数组。
将输入数组Arr[]和长度作为其中的元素数。
函数findMin(intarr[],inti,intj)获取数组及其索引并返回arr[i+1]到arr[j]之间最小元素的索引。
取一个变量minpos。
如果i和j相同,则返回i作为最小元素的索引,因为它们相同。
否则,使用minpos=findMin(arr,i+1,j)递归查找位置i+1到j。
if(arr[i]<arr[minpos])然后设置{minpos=i;}并返回minpos。
函数recurselectSort(intarr1[],intlen1,intpos1)获取输入数组并使用选择排序中的递归按升序对其进行排序。
如果pos1==len1则没有找到最小值,则返回。
否则设置minpos1=findMin(arr1,pos1,len1-1)
如果当前pos1索引和最小元素索引minpos1不同,则使用temp交换这些索引中的元素。
使用recurselectSort(arr1,len1,pos1+1)对数组的其余部分进行递归。
在所有调用结束时,当len变为1时,我们将退出递归并对数组进行排序。
在main中打印排序后的数组。
示例
#include <iostream> using namespace std; int findMin(int arr[], int i, int j){ int minpos; if (i == j){ return i; } minpos = findMin(arr, i + 1, j); if(arr[i]<arr[minpos]){ minpos=i; } return (minpos); } void recurselectSort(int arr1[], int len1, int pos1){ int temp; int minpos1; if (pos1 == len1){ return; } minpos1 = findMin(arr1, pos1, len1-1); if (minpos1 != pos1){ temp=arr1[pos1]; arr1[pos1]=arr1[minpos1]; arr1[minpos1]=temp; } recurselectSort(arr1, len1, pos1 + 1); } int main(){ int Arr[] = {1,5,3,0,9,3,5}; int length = sizeof(Arr)/sizeof(Arr[0]); recurselectSort(Arr,length,0); cout<<"使用递归选择排序的排序数组: "<<endl; for (int i = 0; i<length ; i++){ cout << Arr[i] << " "; } return 0; }输出结果
如果我们运行上面的代码,它将生成以下输出
使用递归选择排序的排序数组: 0 1 3 3 5 5 9