整理定义

复述展开

选择排序（selection sort）

• 稳定性：不稳定

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

• 排序方式：in-place

选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都排序完成。

选择排序的步骤如下：

1. 遍历待排序序列，将第一个元素设为当前最小（或最大）元素。

2. 从剩余的未排序元素中找到最小（或最大）的元素，与当前最小（或最大）元素进行交换。

3. 将当前最小（或最大）元素放到已排序序列的末尾。

4. 重复步骤2和步骤3，直到所有元素都排序完成。

选择排序的特点是每次选择最小（或最大）元素放到已排序序列的末尾，因此每一轮选择排序都会确定一个元素的最终位置。选择排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。尽管选择排序的时间复杂度较高，但它的实现简单，对于小规模的数据集仍然是一个有效的排序算法。

需要注意的是，选择排序是一种不稳定的排序算法，即相等元素的相对顺序可能会发生改变。如果需要稳定的排序算法，可以考虑其他算法，如插入排序或归并排序。

动态图展示

代码演示

class SelectionSort:
    def selection_sort(self, nums):
        for i in range(len(nums)-1):
            min_index = i
            for j in range(i+1, len(nums)):
                # 寻找 i~n 中最小的数，然后放置到 i
                if nums[min_index] > nums[j]:
                    min_index = j
            # 交换
            if min_index != i:
                nums[min_index], nums[i] = nums[i], nums[min_index]
        return nums


if __name__ == '__main__':
    nums = [10, 13, 2, 33, 3, 4, 4, 7, 9]
    solution = SelectSort()
    print(solution.select_sort(nums))

理解体会

首先，选择排序是一种简单但有效的排序算法。它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，将其放置在已排序序列的末尾，逐步构建有序序列。选择排序的过程可以分为两个子操作：选择和交换。

选择排序的优点是实现简单，代码量少，不需要额外的空间。它适用于小规模的数据集，对于简单的排序任务是一个有效的选择。此外，选择排序是一种不稳定的排序算法。当存在相等元素时，选择排序可能会改变它们的相对顺序。这是因为选择排序每次选择最小（或最大）元素进行交换，可能会导致相等元素的位置发生变化。

总结来说，选择排序是一种简单但有效的排序算法。它通过选择和交换操作逐步构建有序序列。尽管选择排序的时间复杂度较高且不稳定，但在小规模数据集上仍然是一个可行的排序算法。对于理解排序算法的基本原理和实现细节，选择排序是一个很好的起点。