ruby - Ruby 中的快速排序不稳定是什么意思(并暗示)？

Question

正在使用一些 Ruby 代码来重新排列图像的像素并遇到奇怪的效果。

下面的代码载入一个图像，将像素读入数组，重新排序像素(以一种意想不到但显然有效的方式使用 Array.sort)，然后创建另一个图像它使用与原始图像相同的尺寸写出重新排序的像素。

根据这个:How does Ruby's max function order duplicates?不稳定意味着结果不可预测。然而，每次我使用相同的输入运行代码时，我都会得到相同的输出，所以从这个意义上说，这种情况下的排序结果是可以预测的。

排序算法不稳定是什么意思，在这种情况下如何应用？

代码仅在使用以下版本的 Mac 上进行了测试:ruby 2.5.1p57(2018-03-29 修订版 63029)[x86_64-darwin16]。

require 'rmagick'

include Magick

img = ImageList.new("images/test-image.jpg")
pixels = img.get_pixels(0,0,img.columns,img.rows)

# https://apidock.com/ruby/Array/sort
# The block must implement a comparison between a and b and
# * <0 when b follows a,
# * 0 when a and b are equivalent, 
# * >0 when a follows b

# The result is not guaranteed to be stable.
# When the comparison of two elements returns 0, the order of the elements is unpredictable.

pixels = pixels.sort {|p| 1 }

out_img = Magick::Image.new(img.columns, img.rows)
out_img.store_pixels(0,0, img.columns, img.rows, pixels)
out_img.write("images/test-image-out.jpg")

输入图像:

输出图像:

此外，还有一个相关问题:https://dsp.stackexchange.com/questions/60106/how-would-you-interpret-the-pattern-in-this-picture-generated-by-re-sorting-pi

Answer 1

非稳定性不是排序对于相同的输入列表会给出不同的结果。这是当您按某种顺序对输入列表进行排序时，根据顺序等价的元素不能保证在输出中相对于彼此位于相同的位置作为输入。

例如，按整数年龄对一排人进行排序。对于队列中相同年龄的人，没有办法选择谁应该排在第一位、第二位等等:他们是等价的。稳定排序的输出会保留它们在输入行中的相对位置。比如说，Alice 和 Bob 都是 43 岁，而 Bob 在原来的行中领先于 Alice。稳定的排序保证 Bob 在输出行中领先于 Alice。不稳定的排序不会。

“不可预测”的评论有点误导。如果有足够的关于算法的信息，或者它在相同输入下的表现，它是可以预测的。然而，如果你只知道它是一种不稳定的类型，那么它就不是。具体来说，等效元素的排序方式是不可预测的。