C++递归实现选择排序算法

实现选择排序算法的递归版本，步骤如下：

步骤1：找到最小值

首先，在要排序的数组中找到最小值，这个过程可以用for循环来实现。具体实现如下：

// 找到数组中最小值的下标
int findMinIndex(int arr[], int startIndex, int endIndex)
{
    int minIndex = startIndex;
    for (int i = startIndex + 1; i <= endIndex; i++)
    {
        if (arr[i] < arr[minIndex])
        {
            minIndex = i;
        }
    }
    return minIndex;
}

步骤2：递归

然后，用递归实现选择排序算法。递归的过程如下：

• 每次找到当前范围内（startIndex到endIndex）的最小值；
• 如果这个最小值不是当前范围的第一个数，把这个最小值和范围的第一个数交换位置；
• 把递归范围缩小为startIndex+1到endIndex。

最终，当startIndex>=endIndex时，排序就完成了。

代码实现如下：

// 递归实现选择排序算法
void selectionSortRecursive(int arr[], int startIndex, int endIndex)
{
    if (startIndex >= endIndex) return;   // 递归出口
    int minIndex = findMinIndex(arr, startIndex, endIndex);
    if (minIndex != startIndex)   // 如果最小值不是当前范围的第一个数，交换位置
    {
        int tmp = arr[startIndex];
        arr[startIndex] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    selectionSortRecursive(arr, startIndex + 1, endIndex);   // 缩小递归范围
}

示例1

以数组{3, 2, 1}为例，进行递归选择排序的过程如下：

• 范围是{3, 2, 1}，找到最小值1，与3交换位置，得到{1, 2, 3}。
• 范围是{2, 3}，2是最小值，不需要交换位置。
• 范围是{3}，只有一个数，无需排序。
• 排序完成。

最终结果为{1, 2, 3}。

示例2

以数组{5, 3, 6, 7, 1}为例，进行递归选择排序的过程如下：

• 范围是{5, 3, 6, 7, 1}，找到最小值1，与5交换位置，得到{1, 3, 6, 7, 5}。
• 范围是{3, 6, 7, 5}，找到最小值3，与3交换位置，得到{1, 3, 6, 7, 5}。
• 范围是{6, 7, 5}，找到最小值5，与6交换位置，得到{1, 3, 5, 7, 6}。
• 范围是{7, 6}，6是最小值，不需要交换位置。
• 范围是{7}，只有一个数，无需排序。
• 排序完成。

最终结果为{1, 3, 5, 6, 7}。