双向交替选择排序：一种改进的选择排序算法实现

1. 算法背景与挑战

选择排序（selection sort）是一种简单直观的排序算法。它的基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。本教程将探讨一种变体的选择排序，其核心挑战在于：

• 交替选择策略： 在奇数次迭代中，需要找到当前未排序区间内的某个特定值并将其放置到合适位置；在偶数次迭代中，则需要找到另一个特定值并放置到另一端。
• 动态区间管理： 随着每次迭代完成一个元素的放置，未排序的区间会缩小，需要准确地维护这个区间。
• 正确索引与范围： 错误地使用循环变量作为交换目标索引或在错误的范围内搜索，是实现此类算法时常见的陷阱。

原始实现中，一个常见的错误是将外层循环的迭代变量i直接用作元素交换的目标索引。然而，在双向交替排序中，元素的最终位置并非简单地由当前迭代次数决定，而是由未排序区间的左右边界动态决定。同时，搜索最小或最大元素的范围也必须限制在当前未排序的区间内。

2. 双向交替选择排序的核心逻辑

为了高效地实现这种双向交替选择排序并确保最终列表完全有序，我们引入两个指针 left 和 right 来界定当前未排序的子数组区间。left 指向未排序区间的起始（最左）索引，right 指向未排序区间的结束（最右）索引。每次迭代，我们根据迭代次数的奇偶性，在 [left, right] 区间内找到目标元素并将其放置到 left 或 right 指向的位置，然后相应地收缩 left 或 right 指针。

具体策略如下：

闪念贝壳

闪念贝壳是一款AI 驱动的智能语音笔记，随时随地用语音记录你的每一个想法。

下载

1. 初始化： left 指向数组的第一个元素（索引 0），right 指向数组的最后一个元素（索引 n-1）。
2. 迭代过程： 进行 n-1 次迭代（或直到 left >= right）。在每次迭代中：
   • 奇数迭代 (例如，第1、3、5...次迭代)：
     • 在当前未排序区间 [left, right] 内找到最大元素。
     • 将该最大元素与 arr[right] 处的元素进行交换。
     • 将 right 指针向左移动一位 (right -= 1)，表示最右端的元素已排序。
   • 偶数迭代 (例如，第2、4、6...次迭代)：
     • 在当前未排序区间 [left, right] 内找到最小元素。
     • 将该最小元素与 arr[left] 处的元素进行交换。
     • 将 left 指针向右移动一位 (left += 1)，表示最左端的元素已排序。

这种策略确保了在每次迭代中，一个元素被放置到其最终的排序位置，从而逐步将整个数组排序。

3. 示例代码实现

以下是使用 Python 实现双向交替选择排序的修正代码：

def ordenacao_por_selecao_modificada(arr):
    """
    实现一种改进的选择排序算法，交替地将最大/最小元素放置到数组的两端。

    Args:
        arr (list): 待排序的列表。
    """
    n = len(arr)
    if n <= 1: # 列表为空或只有一个元素，无需排序
        return

    left = 0
    right = n - 1

    # 进行 N-1 次迭代。注意，当 left >= right 时，表示所有元素都已排序。
    # 这里的循环条件也可以是 while left < right
    for i in range(1, n): # i 仅作为迭代计数器
        if left >= right: # 如果区间已重叠或交叉，则排序完成
            break

        if i % 2 == 1:  # 奇数迭代：找到最大值并放置到右端
            # 假设当前区间 [left, right] 的最右端元素是最大的
            indice_maior = right
            # 在 [left, right] 范围内寻找真正的最大值
            for j in range(left, right + 1):
                if arr[j] >