C 语言选择排序

在本文中，我们将讨论 C 语言中的选择排序及其不同的属性和实现。

选择排序是一种简单的排序算法，它通过重复从数组的未排序部分中选择最小（或最大）元素并将其移动到已排序部分的末尾来工作。这个过程会重复进行，直到整个数组被排序。

它是一种基于比较的排序算法。它通过将输入数组分成两部分来工作：已排序部分和未排序部分。在每次迭代中，它从未排序部分中找到最小（或最大，取决于排序顺序）的元素，并将其与未排序部分的第一个元素交换。这个过程会重复进行，直到整个数组被排序。

选择排序是一种直接有效的排序算法，它不断地将列表中未排序部分的最小（或最大）元素移动到列表的已排序部分。

示例

未排序数组：[38, 52, 9, 18, 6, 23, 40, 15]

步骤 1：初始数组

数组分为两部分：已排序部分（初始为空）和未排序部分（所有元素）。

步骤 2：查找最小元素

在第一次迭代中，我们在数组的未排序部分中查找最小元素，即 6。

步骤 3：交换并扩展已排序部分

我们将最小元素 (6) 与未排序部分 (38) 的第一个元素交换。

已排序部分 (6) 已经扩展，未排序部分已经缩小。

步骤 4：对剩余的未排序部分重复

现在，我们对剩余的未排序部分 ([52, 9, 18, 38, 23, 40, 15]) 重复此过程。此部分的最小元素是 9。

步骤 5：再次交换并扩展

我们将最小元素 (9) 与剩余未排序部分的第一个元素 (52) 交换。

已排序部分 (6, 9) 已经扩展，未排序部分已经缩小。

步骤 6：重复步骤 4 和 5

对剩余的未排序部分 ([52, 18, 38, 23, 40, 15]) 重复此过程。最小元素是 15。

步骤 7：再次交换并扩展

将最小元素 (15) 与剩余未排序部分 (52) 的第一个元素交换。

已排序部分 (6, 9, 15) 已经扩展，未排序部分进一步缩小。

步骤 8：重复步骤 4 和 5

对剩余的未排序部分 ([18, 38, 23, 40, 52]) 重复此过程。最小元素是 18。

步骤 9：再次交换并扩展

将最小元素 (18) 与剩余未排序部分的第一个元素 (38) 交换。

已排序部分 (6, 9, 15, 18) 已经扩展，未排序部分进一步缩小。

步骤 10：重复步骤 4 和 5

对剩余的未排序部分 ([38, 23, 40, 52]) 重复此过程。最小元素是 23。

步骤 11：再次交换并扩展

将最小元素 (23) 与剩余未排序部分 (38) 的第一个元素交换。

已排序部分 (6, 9, 15, 18, 23) 已经扩展，未排序部分进一步缩小。

步骤 12：重复步骤 4 和 5

对剩余的未排序部分 ([38, 40, 52]) 重复此过程。最小元素是 38。

步骤 13：再次交换并扩展

将最小元素 (38) 与剩余未排序部分的第一个元素 (40) 交换。

已排序部分 (6, 9, 15, 18, 23, 38) 已经扩展，未排序部分进一步缩小。

步骤 14：最终迭代

最后，我们对剩余的未排序部分 ([40, 52]) 最后一次重复此过程。最小元素是 40。

步骤 15：最后一次交换和扩展

将最小元素 (40) 与剩余未排序部分的第一个元素（40，即相同元素）交换。

整个数组现在已按升序排序。

排序完成

整个数组现在已排序：[6, 9, 15, 18, 23, 38, 40, 52]。

这个详细的示例演示了选择排序如何通过重复从未排序部分中查找最小元素并将其放入已排序部分来工作。每次迭代都会扩展已排序部分并缩小未排序部分，直到整个数组被排序。

程序 1：使用迭代过程

让我们通过一个示例来理解 C 语言中使用迭代过程的选择排序概念。

输出

Original array: 38 52 9 18 6 23 40 15 
Sortеd array: 6 9 15 18 23 38 40 52

说明

• 在这个例子中，代码首先包含标准输入/输出库 ()，这是printf()等函数所必需的。
• 定义了 selectionSort 函数，用于对数组执行选择排序算法。它接受两个参数：数组 arr 和数组的大小 n。
• 外层 for 循环迭代数组元素，从索引 0 到 n - 2。此循环控制将与未排序部分中最小元素交换的元素位置。
• 在外层循环内部，有一个从 i + 1 开始的内层 for 循环，它迭代数组中剩余的未排序部分。它用于查找未排序部分中最小元素的索引。
• minIndex 变量跟踪当前持有最小元素的索引。内层循环将未排序部分中的每个元素与当前 minIndex 处的元素进行比较。如果找到一个更小的元素，minIndex 会更新为该更小元素的索引。
• 在内层循环之后，如果 minIndex 不等于当前索引 i，则表示在未排序部分中找到了一个更小的元素。在这种情况下，会交换索引 i 和 minIndex 处的元素。
• 在 main 函数中，定义了一个示例数组 arr，并使用 sizeof 运算符计算其大小 n。原始数组使用 for 循环打印。
• 调用 selectionSort 函数来排序数组。
• 排序后，使用另一个 for 循环打印排序后的数组。
• main 函数返回 0，表示程序成功执行。
• 此代码演示了选择排序如何通过重复从未排序部分中选择最小元素并将其放置在已排序部分中的正确位置来工作。结果是一个排序数组。

复杂度分析

时间复杂度

在提供的代码中，选择排序算法的时间复杂度为 O(n^2)，其中 "n" 是数组中的元素数量。这是由于嵌套循环：

• 外层循环运行 (n - 1) 次，其中 "n" 是数组中的元素数量。
• 在最坏的情况下，内层循环也运行 (n - 1) 次，因为它从 i + 1 开始并一直到最后一个元素。
• 选择排序的时间复杂度与元素的初始顺序无关，这意味着无论输入的排序程度如何，它都会执行相同数量的比较和交换。

空间复杂度

• 选择排序算法的空间复杂度为 O(1)，这意味着它无论输入大小如何都只需要常量量的额外空间。这是因为该算法在原地执行所有操作，直接修改输入数组。
• 变量（如 i、minIndex 和 temp）所需的内存是常量，并且不依赖于输入大小。

程序 2：使用递归过程

让我们通过一个示例来理解 C 语言中使用递归过程的选择排序概念。

输出

Original array: 38 52 9 18 6 23 40 15 
Sortеd array: 6 9 15 18 23 38 40 52

说明

• 在这个例子中，代码首先包含标准输入/输出库。该库提供了 printf 等函数用于向控制台打印。
• 定义了 swap 函数，用于使用指针交换两个整数的值。它是一个实用函数，稍后在代码中用于交换数组中的元素。
• 定义了 selectionSortRecursion 函数，用于使用递归执行选择排序。它接受三个参数：arr（要排序的数组）、n（数组中的元素数量）和 index（当前正在考虑的索引）。
• 该函数首先检查索引是否大于或等于 n - 1。如果是，函数返回，停止递归。这是基本情况，当整个数组都被遍历时，它终止递归。
• 在递归函数内部，代码找到数组未排序部分中最小元素的索引，从当前索引开始。minIndex 跟踪具有最小元素的索引。
• 一个循环从 index + 1 迭代到数组的末尾 (n)。此循环的目的是查找未排序部分中最小元素的索引。
• 在内层循环中，代码将每个元素的值与 minIndex 处元素的值进行比较。如果找到一个更小的值，minIndex 会更新为该更小元素的索引。这确保 minIndex 指向未排序部分中最小元素的索引。
• 在内层循环之后，代码检查 minIndex 是否与当前索引不同。如果它们不同，则表示在未排序部分中找到了一个更小的元素。在这种情况下，调用 swap 函数来交换索引 index 和 minIndex 处的元素。
• 最后，递归函数对其自身进行递归调用，将下一个索引 (index + 1) 作为参数传递。此递归调用继续选择和放置元素的过程，直到满足基本情况。
• 在 main 函数中，定义了一个示例数组 arr，并使用 sizeof 运算符计算其大小 n。原始数组和排序后的数组都会打印。
• 当代码执行时，它使用选择排序递归地排序数组，并打印原始数组和排序后的数组。

复杂度分析

时间复杂度

递归选择排序算法的时间复杂度为 O(n^2)，其中 "n" 是数组中的元素数量。递归函数有两个嵌套循环：外层循环迭代数组，内层循环也迭代数组中剩余的未排序部分。

然而，算法的递归性质并没有改变其基本的时间复杂度。递归仍然涉及检查所有元素对，进行比较，并可能交换它们。递归调用的次数和迭代次数与迭代版本相同。

空间复杂度

递归选择排序算法的空间复杂度为 O(n)，其中 "n" 是数组中的元素数量。这是由于递归调用堆栈所使用的空间。

在每次递归调用中，函数的参数和局部变量都存储在调用堆栈上。由于算法进行 O(n) 次递归调用（数组中的每个元素一次），因此空间复杂度与递归深度成正比，即 O(n)。

递归函数调用所使用的额外空间是导致空间复杂度的原因，这使其与迭代版本不同，迭代版本的空间复杂度为 O(1)，因为它是在原地操作的。