不破坏原有排序顺序的排序算法有哪些？相关特性名称是什么

排序保留相等元素原有顺序的特性名称 #

这种特性叫稳定性，满足该特性的排序算法被称为稳定排序算法：当排序过程中遇到值相等的元素时，算法不会打乱它们在原序列中的相对先后位置。你之前用到的快速排序就属于不稳定排序，所以才会出现二次排序打乱原有顺序的问题。

适配需求的排序方案 #

你可以选择以下两种高效方案，性能均为O(nlogn)量级，远优于冒泡排序的O(n²)：

• 方案1：使用高效稳定排序算法按type字段二次排序
  常见的高效稳定排序包括归并排序、Timsort，目前绝大多数编程语言的内置排序实现（比如Python、Java、JavaScript V8引擎）都默认采用优化过的稳定Timsort，你直接调用内置排序方法按type字段排序即可，同type分类下的元素会自动保留之前按name排序的顺序。
  示例代码（JavaScript）：

  // 第一步：按name排序
  arr.sort((a, b) => a.name.localeCompare(b.name))
  // 第二步：按type排序，内置排序为稳定排序，保留同type下的name顺序
  arr.sort((a, b) => a.type.localeCompare(b.type))
  

• 方案2：一次多关键字排序
  你也可以直接设置排序优先级，先按type比较，type相等时再按name比较，这种方式只需要做一次排序，效率更高，且即使使用不稳定的快排也能达到需求效果。
  示例代码（JavaScript）：

  arr.sort((a, b) => {
    // 优先按type排序
    if (a.type !== b.type) return a.type.localeCompare(b.type)
    // type相等时按name排序
    return a.name.localeCompare(b.name)
  })
  

内容的提问来源于stack exchange，提问作者xakepp35