选择排序代码实现

什么是选择排序？

选择排序是一种简单直观的比较排序算法。它的基本思想是：遍历数组多次，每次从未排序的部分中找到最小（或最大）元素，将其放到已排序部分的末尾。

算法步骤

1. 外层循环：从第一个元素开始，直到最后一个元素。
2. 内层循环：在当前未排序部分查找最小值的索引。
3. 交换：将找到的最小值与当前未排序部分的第一个元素进行交换。

示例代码实现（Python）

下面是一个简单的 Python 实现：

def selection_sort(arr):
    """
    选择排序算法实现
    :param arr: 待排序数组
    :return: 排序后的数组
    """
    n = len(arr)
    
    for i in range(n):
        # 假设当前索引i为最小值的索引
        min_index = i
        
        # 寻找从i+1开始到末尾的最大元素的索引
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
                
        # 将找到的最小值与当前未排序部分的第一个元素交换位置
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

# 示例使用
if __name__ == "__main__":
    example_array = [64, 25, 12, 22, 11]
    sorted_array = selection_sort(example_array)
    print("排序后的数组:", sorted_array)

性能分析

• 时间复杂度：选择排序的时间复杂度为O(n^2)，其中n是数组的长度。这是因为在最坏的情况下，每次循环都需要遍历整个未排序部分。

• 空间复杂度：选择排序的空间复杂度为O(1)，因为它只需要常数级别的额外空间。

应用场景

尽管选择排序并不是最优的选择，但在某些特定情况下仍然有用：

• 当数据量非常小且已经部分排序时。
• 当内存受限，需要使用原地排序算法。
• 教学和理解基本排序概念时。

结语

选择排序虽然简单直接，但其O(n^2)的时间复杂度决定了它不适合处理大规模数据。在实际应用中，通常会选择其他更高效的排序方法如快速排序、归并排序等。不过学习选择排序有助于理解基本的排序原理和算法设计思想。