数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++递归选择排序
选择排序是一种排序算法，通过从数组开头迭代并用列表中最小的元素替换每个元素来对数据进行排序。随着我们的前进，左侧数组被排序，而右侧数组未排序。每次移动都会通过交换将下一个最小的元素放置到索引的当前位置。
选择排序算法
int arr[5]= { 5,4,2,1,3 };
int i, j ;
从索引 i=0 遍历到 i<数组大小 -1
从索引 j=i+1 遍历到数组大小 - 1
找到最小值并存储其索引 pos
将找到的索引 pos 处的元素与 arr[i] 交换
结束
递归选择排序
找到最小元素的索引
如果找到的最小元素索引等于数组大小，则返回。
否则，将当前元素与最小元素交换
对其余数组（不包括已排序的元素）递归执行上述步骤
示例
输入 − Arr[] = { 5,7,2,3,1,4 }; length=6
输出 − 已排序数组：1 2 3 4 5 7
解释−
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 };
输出 − 已排序数组：1 2 2 3 3
解释 −
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(int arr[], int i, int j) 获取数组及其索引，并返回 arr[i+1] 到 arr[j] 之间最小元素的索引。
获取一个变量 minpos。
如果 i 和 j 都相同，则返回 i 作为最小元素的索引，因为两者相同。
否则，使用 minpos = findMin(arr, i + 1, j) 递归查找位置 i+1 到 j。
如果 (arr[i]<arr[minpos])，则设置 { minpos=i; } 并返回 minpos。
函数 recurselectSort(int arr1[], int len1, int pos1) 获取输入数组，并使用选择排序中的递归按升序对其进行排序。
如果 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<<"Sorted Array using recursive Selection sort: "<<endl;
for (int i = 0; i<length ; i++){
cout << Arr[i] << " ";
}
return 0;
}输出
如果我们运行以上代码，它将生成以下输出
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9
7K+ 次浏览
