递归实现选择排序.
思路:
1.定位数组中的最大元素或最小元素
2.将其与第一个元素交换位置
3.接着将剩余未排序的元素中的最大值或最小值与第二个元素交换位置
4.以此类推,直到排序完成
示例:
[ 8, 5, 1, 9, 3 ] //原始数组
[ 1, 5, 8, 9, 3 ] //3与8交换
[ 1, 3, 8, 9, 5 ] //3与5交换
[ 1, 3, 5, 9, 8 ] //9与8交换
[ 1, 3, 5, 8, 9 ] //排序完成后的数组
代码:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n)
{
//当数组大小为0或1时直接返回
if (n <= 1) {
return;
}
//找到未排序部分最小元素的索引
int minIndex = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
//将最小元素与开头的元素交换位置
swap(arr[0], arr[minIndex]);
//递归的对剩余元素排序
selectionSort(arr + 1, n - 1);
//arr + 1 将指针后移一位,n - 1排除排序的元素
}
int main()
{
//初始化一个数组
int arr[] = { 7,2,1,8,4,9 };
//n的大小
int n = sizeof(arr) / sizeof(arr[0]);
//调用函数
selectionSort(arr, n);
//输出排序后的数组
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}