Java实现Hoare分区快速排序：结果展示问题与代码优化问询

我首次尝试用Java实现基于Hoare分区的快速排序，现在需要优化代码以正确展示排序结果。目前main方法里没调用quicksortHoare方法，直接输出了原始数组test1，导致看不到排序后的结果。想知道要添加哪些内容才能正确显示排序结果，同时希望得到建设性的优化意见。

核心问题修正步骤 #

• 调用排序方法：在输出排序结果前，必须调用quicksortHoare方法对list1进行排序，注意传入的初始左右边界是0和list1.size() - 1
• 输出正确的集合：当前代码输出的是原始数组test1，应该输出排序后的list1——因为排序操作是在ArrayList实例上执行的

额外优化建议 #

• 增加无参入口方法：为简化调用，添加无需手动传边界的重载方法，避免调用者处理索引细节
• 避免固定选首元素为基准：固定选首元素当基准，在数组已排序/接近排序时会让时间复杂度退化到O(n²)，可改成随机选基准或三数取中法
• 处理边界集合：在排序方法开头增加空集合、单元素集合的判断，避免不必要的递归调用
• 提取重复逻辑：把元素交换的代码抽成独立方法，减少代码冗余

修正后的完整代码 #

import java.util.ArrayList;
import java.util.Random;

public class Quicksort<E extends Comparable<E>> {
    
    // 简化调用的重载方法，自动处理边界情况
    public static <E extends Comparable<E>> void quicksortHoare(ArrayList<E> list) {
        if (list == null || list.size() <= 1) {
            return;
        }
        quicksortHoare(list, 0, list.size() - 1);
    }
    
    // 基于Hoare分区的快速排序核心方法
    public static <E extends Comparable<E>> void quicksortHoare(ArrayList<E> list, int l, int r) {
        // 降序排序逻辑
        if (l < r) {
            // 随机选择基准元素，避免已排序数组的性能退化
            int pivotIdx = new Random().nextInt(r - l + 1) + l;
            swap(list, l, pivotIdx);
            
            int pivot = partitionHoare(list, l, r);
            quicksortHoare(list, l, pivot);
            quicksortHoare(list, pivot + 1, r);
        }                   
    }   
    
    // Hoare分区实现
    public static <E extends Comparable<E>> int partitionHoare(ArrayList<E> list, int l, int r) {
        E pivot = list.get(l);
        int i = l - 1;
        int j = r + 1;

        while (true) {
            do {
                i++;
            } while (list.get(i).compareTo(pivot) > 0);

            do {
                j--;
            } while (list.get(j).compareTo(pivot) < 0);

            if (i >= j) {
                return j;
            }

            swap(list, i, j);
        }
                                
    }
    
    // 通用元素交换方法
    private static <E extends Comparable<E>> void swap(ArrayList<E> list, int i, int j) {
        E temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    
    public static void main(String[] args) {
        int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};  

        ArrayList<Integer> list1 = new ArrayList<>();
        for (int num : test1) {
            list1.add(num);
        }
        System.out.println("*** Test 1 ***");
        System.out.println("Original list: " + list1);
        
        // 调用排序方法
        quicksortHoare(list1);
        
        // 输出排序后的集合
        System.out.println("Hoare's quicksort (descending): " + list1);
    }
}

代码说明 #

• 新增无参quicksortHoare方法，自动处理空集合、单元素集合的边界情况
• 添加随机选基准逻辑，优化了已排序数组场景下的性能
• 提取swap方法，减少代码重复
• main方法中正确调用排序方法，并输出排序后的list1实例

内容的提问来源于stack exchange，提问作者Jack Wilson