选择排序 (Selection Sort)
选择排序是一种简单直观的排序算法。它的基本思想是在未排序部分中选择最小（或最大）的元素，并将其放在已排序部分的末尾。这个过程持续进行，直到整个数组都被排序。下面将详细介绍选择排序的工作原理、代码实现以及时间复杂度。
Selection Sort is a simple and intuitive sorting algorithm. The basic idea is to repeatedly find the minimum (or maximum) element from the unsorted portion and move it to the end of the sorted portion. This process continues until the entire array is sorted. Below, we’ll explain how selection sort works, provide a code implementation, and discuss its time complexity.
1. What is Selection Sort and How Does It Work?
[English] Selection sort works by dividing the array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the leftmost unsorted element, moving the boundary of the sorted part one element to the right.
Steps:
- Iterate from the first element to the last.
- For each element, find the smallest element in the unsorted portion.
- Swap this smallest element with the current element.
- Repeat until the entire array is sorted.
Example:
Initial array: [64, 25, 12, 22, 11]
Step 1: Find the minimum in [64, 25, 12, 22, 11] -> 11
Swap 11 with 64
Array: [11, 25, 12, 22, 64]
Step 2: Find the minimum in [25, 12, 22, 64] -> 12
Swap 12 with 25
Array: [11, 12, 25, 22, 64]
Step 3: Find the minimum in [25, 22, 64] -> 22
Swap 22 with 25
Array: [11, 12, 22, 25, 64]
Step 4: Find the minimum in [25, 64] -> 25
No swap needed
Array: [11, 12, 22, 25, 64]
Step 5: Find the minimum in [64] -> 64
No swap needed
Array: [11, 12, 22, 25, 64]
Sorted array: [11, 12, 22, 25, 64]Behind the Scenes: The algorithm searches for the minimum element in the remaining unsorted portion and places it in its correct position in the sorted portion.
[Chinese] 选择排序通过将数组分为两部分：已排序部分和未排序部分来工作。最初，已排序部分为空，未排序部分包含所有元素。算法反复从未排序部分中选择最小（或最大）的元素，并将其与最左边的未排序元素交换，将已排序部分的边界向右移动一个元素。
步骤:
- 从第一个元素到最后一个元素迭代。
- 对于每个元素，在未排序部分中找到最小的元素。
- 将这个最小元素与当前元素交换。
- 重复直到整个数组排序完成。
示例:
初始数组: [64, 25, 12, 22, 11]
步骤 1: 在 [64, 25, 12, 22, 11] 中找到最小值 -> 11
将 11 与 64 交换
数组: [11, 25, 12, 22, 64]
步骤 2: 在 [25, 12, 22, 64] 中找到最小值 -> 12
将 12 与 25 交换
数组: [11, 12, 25, 22, 64]
步骤 3: 在 [25, 22, 64] 中找到最小值 -> 22
将 22 与 25 交换
数组: [11, 12, 22, 25, 64]
步骤 4: 在 [25, 64] 中找到最小值 -> 25
无需交换
数组: [11, 12, 22, 25, 64]
步骤 5: 在 [64] 中找到最小值 -> 64
无需交换
数组: [11, 12, 22, 25, 64]
排序后的数组: [11, 12, 22, 25, 64]Behind the Scenes: 算法在剩余未排序部分中查找最小元素，并将其放置在已排序部分的正确位置。
2. How to Implement Selection Sort in Python?
[English] Here is the Python code to implement the selection sort algorithm.
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Find the minimum element in the unsorted portion
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
# Swap the found minimum element with the first element of the unsorted portion
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# Example usage
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)What Happens: The function selection_sort sorts the input array in ascending order by repeatedly finding the minimum element and placing it at the beginning of the unsorted portion.
Behind the Scenes: The outer loop iterates over each element, while the inner loop finds the minimum element in the unsorted portion and swaps it with the first unsorted element.
[Chinese] 下面是选择排序算法的 Python 实现代码。
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]
return arr
# 示例用法
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("排序后的数组:", sorted_arr)What Happens: 函数 selection_sort 通过反复查找最小元素并将其放在未排序部分的开头来按升序排序输入数组。
Behind the Scenes: 外层循环遍历每个元素，而内层循环在未排序部分中找到最小元素并将其与第一个未排序元素交换。
3. What is the Time Complexity of Selection Sort?
[English] The time complexity of selection sort is O(n^2) where n is the number of elements in the array. This is because for each element, the algorithm must scan through the entire unsorted portion to find the minimum, leading to a quadratic time complexity.
Time Complexity:
- Best Case:
O(n^2)(even if the array is already sorted) - Average Case:
O(n^2) - Worst Case:
O(n^2)
Space Complexity:
- Space Complexity:
O(1)(in-place sorting, no extra space needed)
[Chinese] 选择排序的时间复杂度是 O(n^2)，其中 n 是数组中的元素数量。这是因为对于每个元素，算法必须扫描整个未排序部分以找到最小值，从而导致二次时间复杂度。
时间复杂度:
- 最好情况:
O(n^2)（即使数组已经排序） - 平均情况:
O(n^2) - 最坏情况:
O(n^2)
空间复杂度:
- 空间复杂度:
O(1)（原地排序，不需要额外空间）
4. When Should You Use Selection Sort?
[English] Selection sort is not the most efficient algorithm for large datasets due to its O(n^2) time complexity. However, it can be useful in scenarios where memory space is limited because it is an in-place sorting algorithm. It is also simple to understand and implement, making it a good choice for teaching sorting algorithms.
Use Cases:
- Small datasets: Works well for small lists where the simplicity of implementation outweighs the inefficiency.
- Memory-constrained environments: Since it uses
O(1)extra space, it is suitable for environments with limited memory. - Educational purposes: Ideal for introducing sorting concepts due to its simplicity.
[Chinese] 由于其 O(n^2) 的时间复杂度，选择排序对于大数据集不是最有效的算法。然而，由于它是一种原地排序算法，因此在内存空间有限的情况下可能非常有用。它还简单易懂，易于实现，使其成为教学排序算法的一个不错的选择。
使用场景:
- 小数据集: 适用于小型列表，在实现简单性优于低效性的情况下效果良
Recommend Resources:
Python: SelectionSort algorithm by Oggi AI
Leave a Reply