Java List上的快速排序算法实现与优化指南

import java.util.Objects; // 导入Objects类用于equals和hashCode

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;
    }

    // 推荐重写toString方法，便于调试
    @Override
    public String toString() {
        return "Location{" +
               "zipCode='" + zipCode + '\'' +
               ", city='" + city + '\'' +
               ", state='" + state + '\'' +
               '}';
    }

    // 推荐重写equals和hashCode方法，保持对象一致性
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Location location = (Location) o;
        return Objects.equals(zipCode, location.zipCode); // 仅基于zipCode进行比较，可根据需求调整
    }

    @Override
    public int hashCode() {
        return Objects.hash(zipCode); // 仅基于zipCode进行哈希，可根据需求调整
    }

    /**
     * 比较两个Location对象。
     * 遵循Comparable接口约定：
     * - 如果当前对象小于指定对象，返回负整数。
     * - 如果当前对象等于指定对象，返回零。
     * - 如果当前对象大于指定对象，返回正整数。
     *
     * 这里我们根据邮政编码（zipCode）的数值大小进行升序排序。
     */
    @Override
    public int compareTo(Location o) {
        // 将zipCode从String转换为Integer进行数值比较
        int thisZipCode = Integer.parseInt(this.zipCode);
        int otherZipCode = Integer.parseInt(o.getZipCode());

        // 使用Integer.compare方法进行安全且标准的比较
        return Integer.compare(thisZipCode, otherZipCode);
    }
}

import java.util.Collections; // 导入Collections类用于swap

// ... Location 类及其他代码 ...

public class QuickSortUtil {

    /**
     * 公共入口方法，用于对整个列表进行快速排序。
     * @param locations 待排序的Location对象列表。
     */
    public static void quickSort(List<Location> locations) {
        if (locations == null || locations.size() <= 1) {
            return; // 列表为空或只有一个元素，无需排序
        }
        quickSortRecursive(locations, 0, locations.size() - 1);
    }

    /**
     * 递归的快速排序方法。
     * @param locations 待排序的Location对象列表。
     * @param startIndex 子列表的起始索引。
     * @param endIndex 子列表的结束索引。
     */
    private static void quickSortRecursive(List<Location> locations, int startIndex, int endIndex) {
        if (startIndex >= endIndex) { // 递归终止条件：子列表为空或只有一个元素
            return;
        }

        // 执行分区操作，获取基准元素的最终位置
        int pivotIndex = partition(locations, startIndex, endIndex);

        // 对基准元素左边的子列表进行递归排序
        quickSortRecursive(locations, startIndex, pivotIndex - 1);
        // 对基准元素右边的子列表进行递归排序
        quickSortRecursive(locations, pivotIndex + 1, endIndex);
    }

    /**
     * 分区方法：选择第一个元素作为基准，将小于基准的元素放到左边，大于基准的元素放到右边。
     * @param locations 待排序的Location对象列表。
     * @param startIndex 子列表的起始索引。
     * @param endIndex 子列表的结束索引。
     * @return 基准元素最终的索引位置。
     */
    private static int partition(List<Location> locations, int startIndex, int endIndex) {
        Location pivotValue = locations.get(startIndex); // 选择第一个元素作为基准值
        int smallerIndex = startIndex; // smallerIndex指向最后一个小于或等于基准的元素的索引

        // 遍历从startIndex + 1到endIndex的元素
        for (int biggerIndex = startIndex + 1; biggerIndex <= endIndex; biggerIndex++) {
            // 如果当前元素（locations.get(biggerIndex)）小于基准值
            // 注意：compareTo返回负数表示当前对象小于参数对象
            if (locations.get(biggerIndex).compareTo(pivotValue) < 0) {
                smallerIndex++; // 增加smallerIndex，为下一个小于基准的元素腾出位置
                swapElements(locations, smallerIndex, biggerIndex); // 将当前元素与smallerIndex处的元素交换
            }
        }
        // 循环结束后，smallerIndex指向所有小于基准的元素区域的最后一个元素。
        // 将基准元素（最初在startIndex）与smallerIndex处的元素交换，将其放到正确的位置。
        swapElements(locations, startIndex, smallerIndex);
        return smallerIndex; // 返回基准元素的最终索引
    }

    /**
     * 交换列表中两个元素的位置。
     * @param list 列表。
     * @param firstIndex 第一个元素的索引。
     * @param secondIndex 第二个元素的索引。
     */
    private static void swapElements(List<Location> list, int firstIndex, int secondIndex) {
        Location temp = list.get(firstIndex);
        list.set(firstIndex, list.get(secondIndex));
        list.set(secondIndex, temp);
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.Random; // 用于随机化基准选择

// Location 类（如上所示）
// QuickSortUtil 类（如上所示）

public class QuickSortExample {

    public static void main(String[] args) {
        List<Location> locations = new ArrayList<>();
        locations.add(new Location("90210", 34.09, -118.40, "Beverly Hills", "CA"));
        locations.add(new Location("10001", 40.75, -73.99, "New York", "NY"));
        locations.add(new Location("60601", 41.88, -87.62, "Chicago", "IL"));
        locations.add(new Location("90001", 33.97, -118.25, "Los Angeles", "CA"));
        locations.add(new Location("75201", 32.78, -96.80, "Dallas", "TX"));
        locations.add(new Location("02108", 42.35, -71.06, "Boston", "MA"));

        System.out.println("原始列表:");
        locations.forEach(System.out::println);

        QuickSortUtil.quickSort(locations);

        System.out.println("\n排序后的列表 (按zipCode升序):");
        locations.forEach(System.out::println);

        // 验证排序结果
        // 预期输出顺序: 02108, 10001, 60601, 75201, 90001, 90210
    }
}