保持分区元素顺序的简单快速排序 java 实现

Question

TL;DR 维护左右分区顺序的最简单方法是什么？

所以...

我正在应对 this HackerRank 挑战，但由于挑战状态，我无法满足他们的打印要求...

Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

...我正在尝试编写最简单/优雅的解决方案（不希望创建新数组/列表、旋转多个元素等），这就是我所拥有的...

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 而不是 [=15] =] 因为我的算法没有保持左分区的元素有序（即 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} -> 1不大于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

TL;DR from Wikipedia

Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.

所以...

不幸的是，为了使我的 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;
    }
}

保持分区元素顺序的简单快速排序 java 实现

Simple quicksort java implementation while maintaining partition element order

java

quicksort