如何获得快速排序的分区以产生正确和预期的输出？

Question

这涉及 https://whosebug.com/help/on-topic 中的 "a software algorithm"，在本例中是快速排序算法

这是来自https://www.hackerrank.com/challenges/quicksort1

的练习编码问题（非竞赛）

基本上你应该接受一个列表，比如

4 5 3 7 2

并围绕第一个元素进行分区，在本例中为 4。预期输出为

3 2 4 5 7

但是我得到的输出是

2 3 4 7 5

这是我进行分区的代码（基于 https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-27/20-sorting3-merge-quick.pdf 幻灯片 16 中的学习友好版本）

static void partition(int[] ar) {
       int toPartitionAround = ar[0];
       swap(ar, 0, ar.length - 1);
       int index = partition(ar, 0, ar.length - 2, toPartitionAround);
       swap(ar, index, ar.length - 1);
       printArray(ar);
   }   
   static int partition(int[] ar, int left, int right, int toAround) {
       while(left <= right) {
           while(ar[left] < toAround) {
               left ++;
           }
           while(ar[right] > toAround) {
               right --;
           }
           if(left <= right) {
               swap(ar, left, right);
               left ++;
               right --;
           }
       }
       return left;
   } 

   static void swap(int[] arrayNums, int index1, int index2) {
       int temp = arrayNums[index1];
       arrayNums[index1] = arrayNums[index2];
       arrayNums[index2] = temp;
   }

我可以对此进行修改以匹配预期的输出吗？我在技术上是否仍然得到可能的正确输出，因为我的输出确实遵循属性枢轴左侧的元素小于枢轴并且枢轴右侧的元素大于枢轴？

我所做的是分配主元，将其移动到数组的后面，然后围绕主元划分数组的其余部分（从索引 0 到长度 - 2）。使用此输入，在遍历数组（3 和 5）时发生一次交换。然后，当我从分区结果中获取索引时，我将主元与该结果交换，这意味着我交换了 4 和 5。

我是否遵循类似的过程来获得预期的输出？我看不到要替换什么。

Answer 1

阅读@greybeard 和@Smac89 的评论后，我意识到我需要一种稳定形式的快速排序，稳定如 "preserving the original order of the input set, where the comparison algorithm does not distinguish between two or more items"(https://softwareengineering.stackexchange.com/questions/247440/what-does-it-mean-for-a-sorting-algorithm-to-be-stable)

对我来说，稳定排序对这个运行没有真正意义，因为比较算法确实区分 3 和 2，但是哦，好吧。有人可以澄清一下吗？

我想出的维护相对的解决方案是创建两个 ArrayList，一个用于保存小于或等于主元的值，一个用于保存大于主元的值。这样就保留了相对定位。（2 将在 3 之后，就像在原始列表中一样）。然后，我将两个 ArrayList 中的值连同枢轴一起移回原始枢轴。

如果有人遇到问题，这是我的代码解决方案

 static void partition(int[] ar) {
      List<Integer> smallerValues = new ArrayList<Integer>();
      List<Integer> biggerValues = new ArrayList<Integer>();
      int toPartitionAround = ar[0];
      for(int c=1;c<ar.length;c++) {
          if(ar[c] <= toPartitionAround) {
              smallerValues.add(ar[c]);
          } else {
              biggerValues.add(ar[c]);
          }
      }
      for(int c=0;c<smallerValues.size();c++) {
          ar[c] = smallerValues.get(c);
      }
      ar[smallerValues.size()] = toPartitionAround;
      for(int m=0;m<biggerValues.size();m++) {
          ar[m + smallerValues.size() + 1] = biggerValues.get(m);
      }
      printArray(ar); 
   }

Answer 2

这有点令人困惑，不是吗？我为解决该问题所做的一切就是创建 2 个单独的列表，一个用于存储低于枢轴的元素，另一个用于存储高于枢轴的元素。然后，您只需打印出这些值。这是保留元素顺序并进行 "in-place" 排序的方式。但它也消耗内存。

如何获得快速排序的分区以产生正确和预期的输出？

How to get partition of quicksort to produce the correct and expected output?

java

arrays

algorithm

sorting

quicksort