logo标签列表

快速排序划分方法的稳定性

algorithmquicksort
22
以下是快速排序的划分算法，它是否产生稳定的排序（即是否维护相等值元素的相对位置）：

这个问题

  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])
         
     exchange(A[i+1],A[r]); 
     return i+1;
   }
9
这句话的意思是，当两个元素具有相同的键时（即两个键相等），它会保持它们原来的顺序。 - mawia
2
这是什么编程语言？你的代码中似乎存在拼写错误、括号/方括号错误（以及误导性缩进），而且你的文本中也存在拼写和语法错误。 - Svante
8个回答
44

在某些情况下，您的分区算法将进行一次交换，这将改变相等值的顺序。以下图片帮助展示了您的就地分区算法的工作原理：

Partition Algorithm

我们使用j索引遍历每个值，如果我们看到的值小于分区值，则通过交换它与灰色子数组右侧紧邻元素的位置，将其附加到浅灰色子数组中。浅灰色子数组包含所有<=分区值的元素。现在让我们看看，比如，阶段(c)并考虑三个9位于白色区域开头，后面跟着一个1的情况。也就是说，我们要检查这些9是否<=分区值。我们查看第一个9并发现它不<= 4，因此我们保持它不变，并向前移动j。我们查看下一个9并发现它不<= 4，因此我们也保持它不变，并向前移动j。我们也保持第三个9不变。现在我们查看1并发现它小于分区值，因此我们将其与第一个9交换。然后完成算法时，我们将分区值与i + 1处的值交换，即第二个9。现在我们已经完成了分区算法，并且最初第三个的9现在成为第一个。

请问您能否解释一下在什么情况下它是不稳定的？ - Neel
3
这是一个关于稳定排序的好描述。在稳定排序中，如果两个项目比较相等，则它们的相对顺序将被保留。如果我的示例排序是稳定的，则9会在整个排序过程中保持其顺序。但事实并非如此。第一个和第三个9被交换了位置。交换相等值的情况正是此排序不稳定的条件。那有帮助吗？ - Rose Perrone
Rose Perrone：感谢您的解释。当相等的值被交换时，排序将不再稳定。是否有任何特定的输入模式，可以推导出如果排序后的输入将不稳定？ - Neel
1
有许多输入模式可以交换相等的值。尝试取一个含有三个9和一个1的数组，使用分区值4运行算法，你会发现你会交换9。您可以尝试各种包含重复数字的数组，并观察每当交换导致更改任何重复数字的顺序时。 - Rose Perrone
1
非常清晰。我认为不稳定的例子就在段落中：考虑以下数组，其中4是枢轴，您将看到为什么它是不稳定的。9₁，9₂，9₃，1，4 - vi_ral
20

如果你愿意添加第二个关键字，任何排序方式都可以转换为稳定排序。第二个关键字应该是指示原始顺序的内容，例如一个序列号。在比较函数中，如果第一个关键字相等，则使用第二个关键字。

但是，如果我们遵循上述分区算法，我认为不会有任何稳定性损失，所以您能否提供一组测试数据来证明它是不稳定的。 - mawia
10

当相似元素的原始顺序不改变时，排序是稳定的。由于您的算法交换了相等的元素，因此它不是稳定的。

如果没有交换相等元素，那么它仍然不会是稳定的：

( 1, 5, 2, 5, 3 )

你有两个排序键为“5”的元素。如果因为某种原因比较第2个元素（5）和第5个元素（3），那么5将与3交换，从而违反稳定排序的规则。这意味着仔细选择枢轴元素是不够的，你还必须确保在分区之间复制元素时不会交换原始顺序。

5
你的代码看起来非常类似于wikipedia上给出的示例分区函数，该函数不稳定，因此您的函数可能不稳定。至少，您应确保您的枢轴点r指向等于A[r]的值数组中的最后一个位置。
您可以使快速排序稳定（我不同意Matthew Jones的观点），但不能在其默认和最快（呵呵）的形式下实现。
Martin（请参见评论）正确地指出，在链表上进行快速排序时，您应从第一个元素开始作为枢轴，并将值附加到较低和较高子列表的末尾，而您遍历数组。然而，快速排序应该在简单的数组上工作，而不是在链接列表上工作。快速排序的优点之一是其低内存占用量（因为所有操作都在原地完成）。如果您正在使用链接列表，则已经为所有指向下一个值等的指针等产生了内存开销，而您正在交换这些指针而不是值。
你能否在不改变算法的情况下使快速排序稳定，以至于它不被认为是快速排序？我并非在开玩笑，只是好奇。 - justinhj
3
链表上的快速排序是稳定的。您将第一个元素作为枢轴，然后通过将元素添加到两个部分来进行分区。每个子列表中的相对顺序将得以保留，因此这种快速排序是稳定的。 - Martin v. Löwis
但是，如果我们遵循上面的分区算法，我认为不会有任何稳定性损失，所以您能否提供一组测试数据，以证明其不稳定。 - mawia
2

快速排序不稳定。下面是它不稳定的情况。

5 5 4 8

以第1到5个元素作为枢轴，第一次排序后的结果如下： 4 5 5 8
可以看到两个5的顺序已经改变。如果我们继续排序，它将会改变排序数组中5的顺序。
2
如果您需要一个稳定的O(n*log(n))排序，可以使用归并排序。（顺便说一句，使快速排序稳定的最好方法是选择随机值的中位数作为枢轴。然而，对于所有等价的元素而言，这并不稳定。）
14
如果所有元素都相同时不稳定，那么它就是不稳定的。 - Joe White
@Joe：那个特殊情况可以在O(n)时间内处理，因此不会影响O(n*log(n))的运行时间。 - JP Alioto
2
我猜你的意思是“所有元素相等”。如果所有元素都相同，则只有一种排列方式，根据定义总是排序的。 - MSalters
1
解决此问题的一种方法是不将数组的最后一个元素作为关键字。快速排序是随机算法。 其性能高度取决于选择的关键字。虽然算法定义说我们应该将最后一个或第一个元素作为关键字，但实际上我们可以选择任何元素作为关键字。 因此，我尝试了中值法，它说要取数组的第一个、中间和最后一个元素。对它们进行排序，然后使用中间位置作为关键字。 例如，我的数组是 {9,6,3,10,15}。通过对第一个、中间和最后一个元素进行排序，它将变成 {3,6,9,10,15}。现在使用 9 作为关键字。所以将关键字移到末尾，它将变成 {3,6,15,10,9}。 我们需要注意的是，如果 9 出现多次会发生什么。也就是说，关键字本身出现了多次。 在这种情况下，在将中间索引作为关键字之后，我们需要遍历从关键字到右端之间的元素，并且如果找到任何与关键字相同的元素，即如果在中间位置到末尾之间找到 9，则将该 9 作为关键字。

现在在元素大于9的区域，即在j的循环中，如果找到任何一个9，则将其与小于该区域即i区域的元素交换。你的数组将被稳定排序。

1

来自维基百科：

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

2
但请注意，通过适当的分区算法和选择良好的枢轴元素，可以使其更加稳定（但速度会变慢）。 - jilles de wit
1
因此，这是选择你的毒药，要么少稳定性，要么降低速度。 - Matthew Jones
请问您能否提供一组测试数据，以证明遵循上述分区方案会导致快速排序算法失去稳定性！ - mawia
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接