选择排序是一种简单的排序算法,它通过在每一轮迭代中找到剩余未排序部分中的最小(或最大)元素,并将其与第一个未排序的位置交换来逐步将数组中的元素按照升序或降序排列。以下是选择排序的基本步骤:
初始化:
- 设定两个索引变量
min_index
和i
,分别用于存储当前最小元素的索引和当前遍历到的元素的索引。
- 设定两个索引变量
遍历数组:
- 从第二个元素开始,依次比较剩余的每个元素。
更新最小值索引:
- 如果当前元素比之前找到的最小元素更小(对于升序排序),则更新
min_index
为当前元素的索引。
- 如果当前元素比之前找到的最小元素更小(对于升序排序),则更新
交换元素:
- 在一轮迭代结束后,将当前最小元素与第一个未排序位置的元素交换。
递归过程:
- 将
i
递增,重复以上过程,直到所有元素都已排序。
- 将
以下是一个Python实现选择排序的例子:
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
# 找到剩余未排序部分中的最小元素
for j in range(i+1, len(arr)):
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("Sorted array:", arr)
在这个例子中,我们使用了一个额外的循环来寻找当前最小元素的索引。然后,在每轮迭代结束时,我们将找到的最小元素与第一个未排序位置的元素交换。这样可以确保每次迭代后,至少有一个元素被放置在正确的位置上。