选择排序代码及时间空间复杂度 简单选择排序时间复杂度分析

选择排序（Selection Sort）是一种简单的排序算法，它不断选择未排序部分的最小元素，并将其放置在已排序部分的末尾。以下是选择排序的代码示例以及时间和空间复杂度分析，希望对大家有所帮助。北京木奇移动技术有限公司，专业的软件外包开发公司，欢迎交流合作。

选择排序的代码示例（升序排序）：

def selection_sort(arr):
n = len(arr)
for i in range(n):
# 假设当前位置的元素是最小的
min_index = i

# 在未排序的部分中找到最小元素的索引
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]
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("排序后的数组：", arr)

时间复杂度分析：

选择排序的时间复杂度与输入数据的初始排列无关，因为它总是进行相同数量的比较和交换。在每一轮中，选择排序会找到未排序部分的最小元素，然后将其放置在已排序部分的末尾。因此，无论数据是否有序，选择排序都需要执行 n-1 轮比较和 n-1 轮交换，其中 n 是数组的长度。因此，选择排序的时间复杂度始终为 O(n^2)。

空间复杂度分析：

选择排序是一种原地排序算法，它不需要额外的空间来存储数据，因此其空间复杂度是 O(1)，即常数级别的空间消耗。

总结：选择排序是一种简单但不是特别高效的排序算法，特别适合小型数据集。由于其时间复杂度为 O(n^2)，在大规模数据集上性能相对较差。通常情况下，更高效的排序算法，如快速排序和归并排序，更常被使用。但选择排序的一个优点是，它对于在每次交换时都有特殊需求的情况可能更有用，因为它可以最小化交换操作的次数。