传习Chuanxi

排序算法的稳定性

排序算法的稳定性

理解排序算法的稳定性。

若排序后相等关键字的元素的相对先后与排序前一致，则称该排序算法是稳定的；否则不稳定。稳定性在「先按班级排、再按分数排且同分保持姓名原顺序」这类多关键字场景里很重要。

GESP 四级常给两三种算法名称，问谁稳定；或给相等元素带标签的动画/数组，问排序后标签顺序是否保留。大纲要求掌握的冒泡、插入、选择排序里：冒泡、插入通常视为稳定；选择排序一般不稳定（交换可能把相等元素跳到前面）。

struct Item { int key; char tag; };
// 稳定排序：key 相同时 tag 的先后与输入相同

做题时盯住「相等元素有没有被交换到跨越彼此」即可快速判断。

冒泡排序和插入排序都是稳定的排序算法。

下面关于排序稳定性的描述，正确的是（ ）。

关于排序算法的稳定性，以下说法错误的是（ ）。

对如下 44 个扑克牌进行排序，

struct Card {
    int value;
    char suit; // 花色
};

Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};

使用某排序算法按value排序后，结果为：{3,'D'}, {3,'B'}, {5,'A'}, {5,'C'}，则这个排序算法是稳定的吗？

冒泡排序和插入排序都是稳定排序算法。

某排序算法对如下数据排序（按 score 升序），则下面关于该排序算法稳定性的描述中，说法正确的是（ ）。

  • 初始：(90,′A′),(90,′B′),(80,′C′),(90,′D′)(90, 'A'), (90, 'B'), (80, 'C'), (90, 'D')
  • 排序后：(80,′C′),(90,′A′),(90,′B′),(90,′D′)(80, 'C'), (90, 'A'), (90, 'B'), (90, 'D')

小杨在对“能量晶石”按亮度进行排序。如果两块晶石亮度相同，他希望保持它们在原始序列中的相对顺序。下列关于排序算法稳定性的说法，错误的是（ ）。

选择排序算法在寻找每一轮最小值时，如果遇到相等的元素不进行交换，则选择排序是一种稳定的排序算法。