代码审查：为 QuickSort 中间枢轴生成最坏情况

Question

我已经实现了一个解决方案，旨在使用 Java 中的中间枢轴策略为快速排序生成最坏情况。我的目标是重新排列输入数组，以在排序过程中产生最差的性能。

这是我写的代码：

public class WorstCaseForMiddlePivotQuickSort<E extends Comparable<? super E>> {
    private static <E extends Comparable<? super E>> int partition(List<E> arr, int low, int high) {
        int middlePivotIndex = (low + high) / 2;
        E pivot = arr.get(middlePivotIndex);
        
        int i = low;
        int j = high;
        
        while (i <= j) {
            while (arr.get(i).compareTo(pivot) < 0) {
                i++;
            }
            while (arr.get(j).compareTo(pivot) > 0) {
                j--;
            }
            
            if (i <= j) {
                Collections.swap(arr, i, j);
                i++;
                j--;
            }
        }
        
        return i;
    }
    
    
    private static <E extends Comparable<? super E>> void quickSortUsingMiddlePivot(List<E> arr, int low, int high, List<Integer> partitionIndexHistory) {
        if (low >= high) {
            return;
        }
        int partitionIndex = partition(arr, low, high);
        partitionIndexHistory.add(partitionIndex);
        quickSortUsingMiddlePivot(arr, low, partitionIndex - 1, partitionIndexHistory);
        quickSortUsingMiddlePivot(arr, partitionIndex + 1, high, partitionIndexHistory);
    }
    
    public static <E extends Comparable<? super E>> List<E> generateWorstCaseForQuickSortPivotPoint(List<E> input, Map<Integer, Integer> currentIndexToPreviousIndexMapping) {
        List<E> reverseOrdered = new ArrayList<>(input);
        reverseOrdered.sort(Collections.reverseOrder());
        List<E> worstCase = new ArrayList<>(Collections.nCopies(reverseOrdered.size(), null));
        int inOrderCount = 0;
        while (inOrderCount < worstCase.size()) {
            int whereToPut = (reverseOrdered.size() - inOrderCount - 1) / 2;
            if (worstCase.get(whereToPut) != null) {
                whereToPut = retrieveIndex(whereToPut, currentIndexToPreviousIndexMapping);
            }
            worstCase.set(whereToPut, reverseOrdered.get(inOrderCount));
            currentIndexToPreviousIndexMapping.put(whereToPut, worstCase.size() - inOrderCount - 1);
            inOrderCount++;
        }
        return worstCase;
    }
    
    public static <E extends Comparable<? super E>> void quickSortUsingMiddlePivot(List<E> input, List<Integer> partitionIndexHistory) {
        if (input == null || input.isEmpty()) {
            return;
        }
        quickSortUsingMiddlePivot(input, 0, input.size() - 1, partitionIndexHistory);
    }
    
    private static int retrieveIndex(int currentIndex, Map<Integer, Integer> currentIndexToPreviousIndexMapping) {
        if (!currentIndexToPreviousIndexMapping.containsKey(currentIndex)) {
            return currentIndex;
        }
        return retrieveIndex(currentIndexToPreviousIndexMapping.get(currentIndex), currentIndexToPreviousIndexMapping);
    }
}

这是我非常简单的测试。虽然我的简单测试已经通过，但我仍然担心我的方法的准确性。

import org.junit.jupiter.api.Test;

import java.util.*;

import static org.junit.jupiter.api.Assertions.*;
import static worstcasegenerator.WorstCaseForMiddlePivotQuickSort.generateWorstCaseForQuickSortPivotPoint;
import static worstcasegenerator.WorstCaseForMiddlePivotQuickSort.quickSortUsingMiddlePivot;

class WorstCaseForMiddlePivotQuickSortTest {
    
    private List<Integer> generatePrefixSizeList(int size) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            list.add(i);
        }
        return list;
    }
    
    private void checkIfIsWorstCase(List<Integer> partitionIndexHistory, int size) {
        assertEquals(size - 1, partitionIndexHistory.size());
        for (int i = 0; i < partitionIndexHistory.size(); i++) {
            assertEquals(size - 1 - i, partitionIndexHistory.get(i));
        }
    }
    
    @Test
    void testWorstCaseForMiddlePivotQuickSortGenerator() {
        for (int size = 1; size <= 100; size++) {
            List<Integer> testInput = generatePrefixSizeList(size);
            List<Integer> partitionIndexHistory = new ArrayList<>();
            Map<Integer, Integer> currentIndexToPreviousIndexMapping = new HashMap<>();
            List<Integer> worstCase = generateWorstCaseForQuickSortPivotPoint(testInput, currentIndexToPreviousIndexMapping);
            System.out.println("input size: " + size + " , worst case input : " + worstCase);
            quickSortUsingMiddlePivot(worstCase, partitionIndexHistory);
            System.out.println("partition index history: " + partitionIndexHistory);
            checkIfIsWorstCase(partitionIndexHistory, size);
        }
    }
}

我正在寻求有关此解决方案的正确性和潜在改进的反馈。我特别感兴趣的是优化算法，增强代码可读性，确保索引管理逻辑有效。

如有任何反馈、建议或改进，我们将不胜感激。谢谢！

Answer 1

“...我已经实现了一个解决方案，旨在使用 Java 中的中间枢轴策略生成 QuickSort 最坏情况的场景。...”

作为参考，这里是来自 Wikipedia 的 “Hoare 分区方案” 算法的移植版本。
该方案使用中点枢轴。

我还没有添加任何评论；这些是原件。

class Quicksort {
    // Sorts a (portion of an) array, divides it into partitions, then sorts those
    void quicksort(int[] A, int lo, int hi) {
        if (lo >= 0 && hi >= 0 && lo < hi) {
            int p = partition(A, lo, hi);
            quicksort(A, lo, p); // Note: the pivot is now included
            quicksort(A, p + 1, hi);
        }
    }

    // Divides array into two partitions
    int partition(int[] A, int lo, int hi) {
        // Pivot value
        int pivot = A[ (int) Math.floor((hi - lo)/2) + lo ]; // The value in the middle of the array

        // Left index
        int i = lo - 1;

        // Right index
        int j = hi + 1, t;

        while (true) {
            // Move the left index to the right at least once and while the element at
            // the left index is less than the pivot
            do i = i + 1;
            while (A[i] < pivot);

            // Move the right index to the left at least once and while the element at
            // the right index is greater than the pivot
            do j = j - 1;
            while (A[j] > pivot);

            // If the indices crossed, return
            if (i >= j) return j;

            // Swap the elements at the left and right indices
            t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
    }
}