快速排序的分区方法的稳定性 [英] Stability of quicksort partitioning approach

问题描述

执行以下操作快速排序的分区算法结果在一个稳定的排序（即它保持与相同值的元素的相对位置）：

 分区（A，P，R）
  {
     X = A [R]。
     I = p-1的;
     对于j = p来的r-1
       如果（A [J]＆LT; = X）
          我++;
          交换（A [1]，A [J]。）

       EXCHANG（A [1 + 1]，A [R]）;
     返回I + 1;
   }
 

解决方案

有一种情况下，你的分区算法将一个交换，这将改变相等值的顺序。这里有一个形象，有助于演示如何您就地分割算法的工作：

我们通过每个值与第j索引前进，并且如果我们看到该值是小于分隔值，我们将其追加到光灰子阵列通过与紧接于光右侧的元件交换它-gray子阵。浅灰色的子数组包含了所有的＆LT元素=分区值。现在，让我们来看看，比如说阶段（C），并考虑在其中三个9的是在白色区的起点的情况下，其次是1。也就是说，我们要检查一下是否9的是＆LT; =分区值。我们看第9，看看它是不是＆LT; = 4，所以我们把它留在地方，行军Ĵ前进。我们来看下9，看看它是不是＆LT; = 4，所以我们也把它留在地方，行军Ĵ前进。我们也留下了第三个9位。现在我们看一下1，并认为它是小于分区，所以我们将其交换与第一9。然后完成算法，我们交换在i + 1的，这是第二个9分隔值的值。现在，我们已经完成了分区算法和9的最初三现在第一位。

Does the following Quicksort partitioning algorithm result in a stable sort (i.e. does it maintain the relative position of elements with equal values):

  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;
   }

解决方案

There is one case in which your partitioning algorithm will make a swap that will change the order of equal values. Here's an image that helps demonstrate how your in-place partitioning algorithm works:

We march through each value with the j index, and if the value we see is less than the partition value, we append it to the light-gray subarray by swapping it with the element that is immediately to the right of the light-gray subarray. The light-gray subarray contains all the elements that are <= the partition value. Now let's look at, say, stage (c) and consider the case in which three 9's are in the beginning of the white zone, followed by a 1. That is, we are about to check whether the 9's are <= the partition value. We look at the first 9 and see that it is not <= 4, so we leave it in place, and march j forward. We look at the next 9 and see that it is not <= 4, so we also leave it in place, and march j forward. We also leave the third 9 in place. Now we look at the 1 and see that it is less than the partition, so we swap it with the first 9. Then to finish the algorithm, we swap the partition value with the value at i+1, which is the second 9. Now we have completed the partition algorithm, and the 9 that was originally third is now first.

这篇关于快速排序的分区方法的稳定性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！