Unstable Sort

定义 Definition

Unstable sort（不稳定排序）指一种排序算法：当序列中存在“相等键值”的元素时，排序完成后这些元素之间的原始先后顺序可能被改变。它与 stable sort（稳定排序） 相对。某些算法在特定实现下可能稳定或不稳定，但“unstable”通常强调不保证保持相对顺序。

发音 Pronunciation (IPA)

/ʌnˈsteɪbəl sɔːrt/

例句 Examples

An unstable sort may change the order of equal items.
不稳定排序可能会改变相同元素之间的先后顺序。

When sorting records by last name, using an unstable sort can shuffle people who share the same last name, so a stable sort is safer if you want to preserve their original input order.
当按姓氏对记录排序时，不稳定排序可能会打乱同姓者之间的顺序；如果你希望保留原始输入顺序，使用稳定排序会更安全。

词源 Etymology

unstable 来自 un-（否定前缀，表示“非、不”）+ stable（稳定的，源自拉丁语 stabilis，意为“站得稳、稳固”）。在计算机科学里，stable/unstable 被借用来描述排序算法对“相等键值元素的相对顺序”是否保持不变。sort 源自法语/拉丁语相关词根，含义为“整理、分类、排序”。

相关词 Related Words

• Stable Sort
• Sorting Algorithm
• Key
• Comparator
• Tie
• Quicksort
• Heapsort
• Mergesort
• Insertion Sort
• Record

文学与作品 Literary / Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）中在讨论排序与“稳定性（stability）”时会涉及稳定/不稳定排序的概念。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）在排序主题下讨论多种排序方法及其性质，包含稳定性相关内容。
• Algorithms（Robert Sedgewick & Kevin Wayne）在讲解排序算法时也会对稳定性与不稳定性进行说明与对比。