如何获得quicksort的分区以产生正确和预期的输出？

Question

这涉及https://stackoverflow.com/help/on-topic中的“软件算法”，在本例中是quicksort排序算法

这是一个来自https://www.hackerrank.com/challenges/quicksort1的练习编码问题（非竞争）

4 5 3 7 2

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的评论之后，我意识到我需要一个稳定形式的quicksort，就像“保留输入集的原始顺序，其中比较算法不区分两个或更多项”（https://softwareengineering.stackExchange.com/questions/247440/what-does-it-mean-for-a-sorting-algorith-to-be-stable）那样稳定

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

我想出的维护relative的解决方案是创建两个数组列表，一个用于保存小于或等于pivot的值，另一个用于保存大于pivot的值。这样相对定位就被保留了。（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); 
   }