快速分区方法的稳定性

Question

下面的Quicksort分区算法是否会产生稳定的排序(即它是否保持元素的相对位置具有相等的值):

  partition(A,p,r)
  {
     x=A[r];
     i=p-1;
     for j=p to r-1
       if(A[j]<=x)
          i++;
          exchange(A[i],A[j])

       exchang(A[i+1],A[r]); 
     return i+1;
   }

Answer 1

在一种情况下,您的分区算法将进行交换,这将改变相等值的顺序.这是一个图像,有助于演示您的就地分区算法的工作原理:

我们使用j索引遍历每个值,如果我们看到的值小于分区值,我们通过将其与紧靠浅灰色子阵列右侧的元素交换,将其附加到浅灰色子阵列.浅灰色子阵列包含<=分区值的所有元素.现在让我们来看看阶段(c)并考虑三个9位于白色区域开头的情况,然后是1.这就是说,我们将检查9的是否<=分区值.我们看看前9个并看到它不是<= 4,所以我们把它留在原地,然后向前迈进.我们看看接下来的9,看到它不是<= 4,所以我们也把它留在原地,然后向前迈进.我们还留下了第三个9.现在我们看1并看到它小于分区,所以我们将它与前9交换.然后为了完成算法,我们将分区值与i + 1的值交换,这是第二个9.现在我们已经完成了分区算法,原来第三个的9现在是第一个.

Answer 2

如果您愿意添加第二个密钥,则可以将任何排序转换为稳定排序.第二个键应该是指示原始顺序的东西,例如序列号.在比较函数中,如果第一个键相等,请使用第二个键.

Answer 3

当类似元素的原始顺序不变时,排序是稳定的.您的算法不稳定,因为它交换相同的元素.

如果没有,那么它仍然不稳定:

( 1, 5, 2, 5, 3 )

您有两个元素,排序键为"5".如果由于某种原因比较元素#2(5)和#5(3),那么5将与3交换,从而违反了稳定排序的合同.这意味着仔细选择pivot元素没有帮助,您还必须确保在分区之间复制元素永远不会交换原始顺序.

Answer 4

您的代码看起来与维基百科上给出的样本分区函数非常相似,这是不稳定的,因此您的函数可能不稳定.至少你应该确保你的轴心点r指向等于A [r]的值数组中的最后一个位置.

你可以让quicksort稳定(我不同意Matthew Jones那里)但不是默认和最快(heh)形式.

马丁(见注释)是正确的,你开始为支点的第一个元素和链表上的快速排序 追加,你去通过数组的下限和上限子列表的末尾值.但是,quicksort应该在一个简单的数组而不是链表上工作.快速排序的一个优点是内存占用少(因为一切都在适当的位置).如果您正在使用链接列表,那么您已经为所有指向下一个值的指针等产生了内存开销,并且您正在交换那些而不是值.

Answer 5

来自维基百科：

快速排序是一种比较排序，在有效的实现中，它不是一种稳定的排序。