Java List递归快速排序quickSortRecursive功能异常排查求助

我正尝试让quickSortRecursive方法正常工作，但它无法通过测试用例。排序依据是邮政编码（zipcode）。

Location类代码 #

public class Location implements Comparable<Location> {

    private final String zipCode;
    private final String city;
    private final Double latitude;
    private final Double longitude;
    private final String state;

    public Location(String zipCode, Double latitude, Double longitude, String city, String state) {
        this.zipCode = zipCode;
        this.city = city;
        this.latitude = latitude;
        this.longitude = longitude;
        this.state = state;
    }

    public String getCity() {
        return this.city;
    }

    public String getZipCode() {
        return this.zipCode;
    }

    public Double getLatitude() {
        return latitude;
    }

    public Double getLongitude() {
        return longitude;
    }

    public String getState() {
        return state;
    }
    

    @Override
    public int compareTo(Location o) {
        int result = 0;
        if(Integer.parseInt(this.zipCode) > Integer.parseInt(o.getZipCode())) {
            result = -1;
        }
    
        if(Integer.parseInt(this.zipCode) < Integer.parseInt(o.getZipCode())) {
            result = 1;
        }
        
        return result;
    }
}

以上是我的Location类及其compareTo方法，该方法实现了邮政编码的降序排序逻辑。

排序方法代码 #

下面是无法正常工作的quickSort方法，而我的insertionSort方法可以完美运行：

public static void quickSortRecursive(List<Location> list, int from, int to) {
        if (from < to) {
            int pivot = from;
            int left = from + 1;
            int right = to;
            Location pivotValue = list.get(pivot);
            while (left <= right) {
                while (left <= to && pivotValue.compareTo(pivotValue) < left) {
                    left++;
                }
                while (right > from && pivotValue.compareTo(pivotValue) > right) {
                    right--;
                }
                if (left < right) {
                    Collections.swap(list, left, right);
                }
            }
            Collections.swap(list, pivot, left - 1);
            quickSortRecursive(list, from, right - 1); 
            quickSortRecursive(list, right + 1, to);  
        }
    }

public static void quickSort(List<Location> locations) {
        quickSortRecursive(locations, 0, locations.size() - 1);
    }


    public static  void insertionSort(List<Location> locations) {
          for (int j = 1; j < locations.size(); j++) {
              Location current = locations.get(j);
                int i = j-1;
                while ((i > -1) && ((locations.get(i).compareTo(current)) == 1)) {
                    locations.set(i+1, locations.get(i));
                    i--;
                }
                locations.set(i+1, current);
            }
    }

问题分析与修正 #

1. 快速排序核心逻辑错误 #

你的quickSortRecursive方法存在三个致命逻辑错误：

• 比较对象错误：pivotValue.compareTo(pivotValue)是将基准元素与自身比较，结果永远为0，再与索引值left/right比较完全没有意义，直接导致指针移动逻辑失效。
• 指针交换后未移动：交换left和right位置的元素后，没有递增left和递减right，可能陷入死循环。
• 递归范围错误：基准元素交换后的位置处理不正确，导致递归范围划分错误。

2. 修正后的快速排序方法 #

public static void quickSortRecursive(List<Location> list, int from, int to) {
    if (from < to) {
        int pivotIndex = from;
        Location pivotValue = list.get(pivotIndex);
        int left = from + 1;
        int right = to;

        while (left <= right) {
            // 从左往右找第一个比基准小的元素（按compareTo的降序逻辑）
            while (left <= right && list.get(left).compareTo(pivotValue) <= 0) {
                left++;
            }
            // 从右往左找第一个比基准大的元素
            while (right >= left && list.get(right).compareTo(pivotValue) > 0) {
                right--;
            }
            // 交换左右指针元素，同时移动指针
            if (left < right) {
                Collections.swap(list, left, right);
                left++;
                right--;
            }
        }
        // 将基准元素放到正确的位置
        Collections.swap(list, pivotIndex, right);
        // 递归排序左右子数组
        quickSortRecursive(list, from, right - 1);
        quickSortRecursive(list, right + 1, to);
    }
}

3. 简化compareTo方法 #

原compareTo方法可以简化为更简洁的写法，逻辑完全一致：

@Override
public int compareTo(Location o) {
    // 实现邮政编码降序排序，如需升序则交换两个参数位置
    return Integer.compare(Integer.parseInt(o.getZipCode()), Integer.parseInt(this.zipCode));
}

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