保持分区元素顺序的简单quicksort java实现

Question

...我正在尝试写一个我能写的最简单/优雅的解决方案（更喜欢不创建新的数组/列表，旋转多个元素等），下面是我的...

import java.io.*;
import java.util.*;

public class Solution {
  public static void main(String[] args) {
    final int n;
    final int[] arr;
    
    try(final Scanner scanner = new Scanner(System.in)) {
        n = scanner.nextInt();
        arr = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
    }
    
    quickSort(arr, 0, n - 1);    
}

private static void quickSort(final int[] arr, final int start, final int end) {
    if(start >= end) return;
    
    final int partitionIndex = partition(arr, start, end);
    
    quickSort(arr, start, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, end);
    
    for(int i = start; i <= end; i++) {
        System.out.print(arr[i] + " ");
    }
    
    System.out.println();
}

private static int partition(final int[] arr, final int start, final int end) {
    final int pivot = arr[start];
    int pivotIndex = end + 1;
    
    for(int i = end; i > start; i--) {
        if(arr[i] > pivot) {
            pivotIndex--;
            final int temp = arr[pivotIndex];
            arr[pivotIndex] = arr[i];
            arr[i] = temp;
        }    
    }
    
    pivotIndex--;
    arr[start] = arr[pivotIndex];        
    arr[pivotIndex] = pivot;
    
    return pivotIndex;
  }
}

...我的提交失败了，因为我的第一个分区不是{1,3,2,5,8,7,9}而是{3,2,1,5,8,7,9}，所以在以后的分区中，我的第一次合并是1 2而不是2 3，因为我的算法没有保持左分区元素的顺序（即1,3,2)。

我的算法从结束到开始迭代，不包括起始元素（枢轴）...

{5,8,1,3,7,9,2}->数据透视为5，数据透视索引为7（超出界限）

{5,8,1,3,7,9,2}->2不大于5，跳过

{5,8,1,3,7,9,2}->9大于5，透视索引为6，交换9和2

{5,8,1,3,7,2,9}->7大于5，透视索引为5，交换7和2

{5,8,1,3,2,7,9}->3不大于5，跳过

{5,8,1,3,2,7,9}->8大于5，透视索引为4，交换8和2

{5,2,1,3,8,7,9}->透视索引为3，交换5和3

{3,2,1,5,8,7,9}->第一个分区后的最终结果

...我保持了右分区的顺序（即8 7 9)，而不是左分区...

Answer 1

维基百科博士

Quicksort的有效实现不是稳定的排序，这意味着不保留相等排序项的相对顺序。

所以...

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        final int n;
        final int[] arr;

        try(final Scanner scanner = new Scanner(System.in)) {
            n = scanner.nextInt();
            arr = new int[n];

            for(int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
        }

        quickSort(arr, 0, n - 1);
    }

    private static void quickSort(final int[] arr, final int start, final int end) {
        if(start >= end) return;

        final int partitionIndex = partition(arr, start, end);

        quickSort(arr, start, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, end);

        for(int i = start; i <= end; i++) {
            System.out.print(arr[i] + " ");
        }

        System.out.println();
    }

    private static int partition(final int[] arr, final int start, final int end) {
        final int pivot = arr[start];
        int pivotIndex = start;

        for(int i = start + 1; i <= end; i++) {
            if(arr[i] < pivot) {
                pivotIndex++;
            }
        }

        int smallerIndex = start;
        int biggerIndex = pivotIndex + 1;
        final int[] copy = Arrays.copyOf(arr, arr.length);

        for(int i = start + 1; i <= end; i++) {
            if(copy[i] < pivot) {
                arr[smallerIndex++] = copy[i];
            } else if(arr[i] > pivot) {
                arr[biggerIndex++] = copy[i];
            }
        }

        arr[pivotIndex] = pivot;

        return pivotIndex;
    }
}