选择排序说明

Question

我一直在研究 C 中的递归函数，它接受一个 int 数组及其大小，并进行选择排序，现在数组应该从最小到最大排序：

void selection_sort(int integers[], size_t size)
{
    if (size == 0) {
        return;
    }

    int largest = 0;
    int largest_index = 0;
    int temp;

    for (int i = 0; i < size; ++i) {
        if (integers[i] > integers[largest_index]) {
            largest_index = i;
        }
    }
    temp = integers[largest_index];
    integers[largest_index] = integers[size - 1];
    integers[size - 1] = temp;

    selection_sort(integers, size - 1);
}

因此，如果整数包含 17、8、14、25 和 11，在调用 selection_sort 后，它现在将包含 8、11、14、17 和 25。代码可以正常工作，但是，我试图在纸上找出逻辑，但我认为我没有正确考虑它，因为我没有得到我应该得到的数字。我想知道是否有人可以逐步彻底解释函数的逻辑。如有任何帮助，我们将不胜感激！

Answer 1

让我们分解您的代码以了解其工作流程。

你的函数有两个参数，一个是数组，另一个是数组的大小

selection_sort(int integers[], size_t size)

第二部分，如果数组的大小为零则 return

if (size == 0) {
        return;
    }

第三部分，定义变量

int largest = 0; //this variable is not used
int largest_index = 0; //this is index for largest array value
int temp; //temporary variable for swapping

第四部分查找数组中的最大值索引

for (int i = 0; i < size; ++i) { //Iterate array from 0 to size
        if (integers[i] > integers[largest_index]) { /*check if current index value is greater than largest value index */
            largest_index = i; /* if value is greater than current index value add index in largest_index variable */
        }

在数组 [17, 8, 14, 25, 11] 的第一次迭代中 largest_index 将是 3 (25)。

第五部分，交换数组的最高值和最后一个元素

[17, 8, 14, 25, 11] 将变为 [17, 8, 14, 11, 25]

 temp = integers[largest_index]; //take 25 in temp
    integers[largest_index] = integers[size - 1]; 
    integers[size - 1] = temp; //swap 11 with 25

最后一部分，递归调用函数，数组大小减少1个元素

示例在第一次迭代数组将 [17, 8, 14, 11] 和第二次迭代 [11, 8, 14] 中，它将不断减小数组大小直到它 returns（大小变为零）

selection_sort(integers, size - 1);

选择排序说明

Selection Sort Explanation

c

algorithm

recursion

selection-sort