Ruby 中的快速排序不稳定是什么意思（并暗示）？

Question

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

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

据此：不稳定意味着结果不可预测。然而，每次我运行使用相同输入的代码，我都会得到相同的输出，所以从这个意义上说，这种情况下的排序结果是可以预测的。

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

该代码仅在 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。不稳定的排序不会。

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

Ruby 中的快速排序不稳定是什么意思（并暗示）？

What does it mean (and imply) that quicksort in Ruby is not stable?

ruby

sorting

imagemagick

image-processing

quicksort