Algorithms 101: Is Selection Sort Stable

选择排序是稳定的吗？

Understanding Stability in Sorting Algorithms 理解排序算法中的稳定性

In the context of sorting algorithms, stability refers to whether the algorithm preserves the relative order of records with equal keys (i.e., if two elements are equal, they should appear in the same order in the sorted output as they do in the input).
在排序算法的上下文中，稳定性指的是算法是否保持具有相同键的记录的相对顺序（即，如果两个元素相等，它们在排序后的输出中应该与输入中的顺序相同）。

• Stable Sorting Algorithm: A sorting algorithm is considered stable if it preserves the relative order of equal elements.
  稳定的排序算法：如果一个排序算法保持相等元素的相对顺序，则认为它是稳定的。

• Unstable Sorting Algorithm: If a sorting algorithm does not guarantee the relative order of equal elements, it is considered unstable.
  不稳定的排序算法：如果一个排序算法不保证相等元素的相对顺序，则认为它是不稳定的。

Is Selection Sort Stable? 选择排序是稳定的吗？

Selection Sort is not stable.
选择排序是不稳定的。

Why is Selection Sort Unstable? 为什么选择排序不稳定？

Selection Sort is unstable because it can change the relative order of equal elements during the sorting process.
选择排序不稳定，因为它可能在排序过程中改变相等元素的相对顺序。

Example of Unstable Behavior 不稳定行为的示例

Consider the following list of tuples where the first element is the key for sorting, and the second element represents an identifier:
考虑以下元组列表，其中第一个元素是排序的键，第二个元素代表标识符：

arr = [(4, 'a'), (3, 'b'), (3, 'c'), (1, 'd')]

Step-by-Step Process of Selection Sort 选择排序的分步过程

1. Initial List: [(4, 'a'), (3, 'b'), (3, 'c'), (1, 'd')]
   初始列表：[(4, 'a'), (3, 'b'), (3, 'c'), (1, 'd')]

2. First Iteration:
   第一次迭代：

   • The minimum element 1 is found and swapped with the first element 4.
     最小元素 1 被找到并与第一个元素 4 交换。

   List after Step 1: [(1, 'd'), (3, 'b'), (3, 'c'), (4, 'a')]
   第1步后的列表：[(1, 'd'), (3, 'b'), (3, 'c'), (4, 'a')]

3. Second Iteration:
   第二次迭代：

   • The next minimum element 3 is already in place, so no swap is needed.
     下一个最小元素 3 已经在原位，所以不需要交换。

   List after Step 2: [(1, 'd'), (3, 'b'), (3, 'c'), (4, 'a')]
   第2步后的列表：[(1, 'd'), (3, 'b'), (3, 'c'), (4, 'a')]

4. Third Iteration:
   第三次迭代：

   • The next minimum element 3 (with identifier 'c') is in place, but the algorithm swaps it with the element 3 (with identifier 'b').
     下一个最小元素 3（标识符为 'c'）在原位，但算法将其与元素 3（标识符为 'b'）交换。

   List after Step 3: [(1, 'd'), (3, 'c'), (3, 'b'), (4, 'a')]
   第3步后的列表：[(1, 'd'), (3, 'c'), (3, 'b'), (4, 'a')]

Analysis 分析

• Original Order: Before sorting, the elements with keys 3 are in the order [(3, 'b'), (3, 'c')].
  原始顺序：在排序之前，键为 3 的元素顺序为 [(3, 'b'), (3, 'c')]。

• After Sorting: The elements with keys 3 have changed their order to [(3, 'c'), (3, 'b')] after sorting.
  排序后：键为 3 的元素在排序后顺序变为 [(3, 'c'), (3, 'b')]。

This change in relative order indicates that Selection Sort is unstable.
这种相对顺序的变化表明选择排序是不稳定的。

Conclusion 结论

Selection Sort is an effective algorithm for small datasets and has a straightforward implementation. However, it is not stable, meaning it can change the relative order of equal elements during the sorting process.
选择排序是一种对小数据集有效且实现简单的算法。然而，它不是稳定的，意味着在排序过程中可能会改变相等元素的相对顺序。

If stability is a requirement for your sorting task (e.g., when sorting records based on multiple fields), you may want to choose a different algorithm, such as Merge Sort or Insertion Sort, which are stable.
如果排序任务需要稳定性（例如，当基于多个字段对记录进行排序时），您可能需要选择不同的算法，例如归并排序或插入排序，它们是稳定的。