Ruby中的quicksort不稳定是什么意思（暗示）？

Question

在玩一些Ruby代码来重新排序图像像素，并遇到了怪异的效果。

下面的代码加载一幅图像，将像素读取到一个数组中，对像素进行Array.sort重新排序（使用意外的但显然有效的方式），然后创建另一个图像，使用相同的图像将重新排序的像素写入该图像原始图片的尺寸。

据此：Ruby的max函数顺序如何重复？不稳定意味着结果不可预测。但是，每次我使用相同的输入运行代码时，都会得到相同的输出，因此从这种意义上说，这种情况下的排序结果是可预测的。

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

该代码仅在使用以下操作系统的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

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

假设，通过增加整数年龄来对一行人进行排序。对于同一年龄段的人，没有办法选择谁应该是第一，第二等：他们是等效的。稳定排序的输出将保留它们在输入行中的相对位置。假设爱丽丝和鲍勃都是43岁，而鲍勃在原先的行列中领先于爱丽丝。稳定的排序可确保Bob在输出行中领先于Alice。不稳定的排序不会。

“无法预测”的说法有些误导。如果有足够的有关算法的信息，或在相同输入下的行为方式，则可以预测。但是，如果您只知道它是一种不稳定的类型，则不是。具体而言，如何对等价元素进行排序是不可预测的。