下面的算法稳定吗？

Question

这个算法稳定不？我检查了稳定的含义并在此站点上找到了一些东西。如果我理解正确，当具有相同键的 2 个事物以相同的顺序出现在输入中以及排序的输出中时，某些事物（我们谈论排序算法）是稳定的。

下面的算法就是大家熟知的Bubblesort。我会说它是稳定的，因为我看不到 2 个相等的元素曾经在那里交换过，因此它必须是稳定的算法。我说得对吗？够了"proof"吗？

Input: Array arr with n integers
Output: Array arr sorted upward
repeat
   swapped = false
   for i = 1 to n-1 do
      if arr[i] > arr[i+1] then
         temp = arr[i]
         arr[i] = arr[i+1]
         arr[i+1] = temp
         swapped = true
      end if
   end for
until not swapped

Answer 1

是的，它很稳定。如果你用

实现它

if arr[i] >= arr[i+1] then

那你就会失去稳定性。

也是，稳定的意思是：当 2 个具有相同键的事物在输入中以相同的顺序出现时，也在排序的输出中出现。当您首先按 key1 排序然后按 key2

排序时，您需要稳定的排序算法

下面的算法稳定吗？

Is the following algorithm stable?

sorting

algorithm

proof