快速分类不能变成稳定分类吗？ [英] Can't quick sort become stable sort?

问题描述

方法1

CAR Hoare引入了分区逻辑（如下所示），这是在学校教的，

  low =枢轴= 0; 
 i = 1; 
 j =高= listSize-1; 
 
 while（true）{
 while（a [i]< = a [pivot]&&（i< high））{
i = i + 1 ; 
} 
而（a [j]> = a [pivot]&&（j>低））{
 j = j-1; 
} 
 
如果（i> = j）
休息； 
 swap（a [i]，a [j]）
} 
 
 swap（a [j]，a [pivot]）; //定位枢轴元素（一次）
 return j; 
  

---

方法2

要基本上尝试使其稳定排序，而不是 j 指向最后一个索引（ listSize- 1 ），如果 j 指向 listSize / 2 （即 mid ），然后

我们进入 j>高或 i> =中，其中 a [i] 没有对应的 a [j] 与 vice-versa 交换。在这种情况下，将 a [i] 与 a [pivot] 交换也没有意义， ，

---

我的问题：

使用方法2

通过保持快速排序的本质，我们是否可以使用数据透视元素（在任何索引处）进行分区？ / p>

注意：分析快速排序，而不是家庭作业

解决方案

这看起来像是家庭作业，所以我不会完全解决它：

• 快速排序可以通过确保没有两个元素比较相等而保持稳定。




• 仅选择一个不同的枢轴并不能提供解决方案。

由于您说的不是家庭作业，因此如何使快速排序稳定：

• 创建一个指向原始数组的指针数组。



• 使用快速排序功能对这个数组进行排序这样比较指针值的方法：

    int sortptr（const void * a，const void * b）{
   const my_type * const * pa = a; 
   const my_type * const * pb = b; 
   int cmp = original_compare_function（* pa，* pb）; 
   return cmp吗？ cmp：（pa> pb）-（pa< pb）； 
  } 
    




• 将已排序的项目复制到已排序的数组中。

请注意，这种方法可以在适当的地方起作用，但是这样做很棘手，并且仍然需要分配数组指针。 merge-sort对于稳定的排序更为可靠，但是需要的工作空间大约是原始数组大小的一半。

Approach 1

C.A.R Hoare introduced partitioning logic(shown below), which is taught in school,

low = pivot = 0;
i = 1;
j = high = listSize-1;

while (true) {
    while (a[i] <= a[pivot] && (i < high)) {
        i = i + 1;
    }
    while (a[j] >= a[pivot] && (j > low)) {
        j = j - 1; 
    }

    if (i >= j)
        break;
    swap(a[i], a[j])
}

swap(a[j], a[pivot]); // pivot element is positioned(once)
return j;

---

Approach 2

To basically try make it stable sort, Instead j pointing to last index(listSize-1), if j points to listSize/2(i.e., mid), then,

we get into scenario where j > high or i >= mid, where a[i] do not have corresponding a[j] to swap with and vice-versa. In such scenario, swapping a[i] with a[pivot] also does not make sense, which looks an incorrect approach, To confirm the same,

---

My question:

With approach 2,

By maintaining the essence of quick sort, Can't we partition with pivot element(at any index)?

Note: Analyzing quick sort, not a home work

解决方案

This looks like home work, so I am not going to solve it completely:

• quick-sort can be made stable by ensuring that no 2 elements compare equal.

• choosing a different pivot alone does not provide a solution for this.

Since you say this is not homework, here is how to make quick-sort stable:

• make an array of pointers to the original array.

• use quick-sort to sort this array with a function that compares the pointed values this way:

  int sortptr(const void *a, const void *b) {
      const my_type * const *pa = a;
      const my_type * const *pb = b;
      int cmp = original_compare_function(*pa, *pb);
      return cmp ? cmp : (pa > pb) - (pa < pb);
  }
  

• copy the sorted items into a sorted array.

Note that this approach can be made to work in place, but it is tricky to do so and would still require allocating the array of pointers. merge-sort is much more reliable for stable sorting, but requires working space of approximately half the size of the original array.

这篇关于快速分类不能变成稳定分类吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！