17370845950

新闻动态
Java中自定义对象列表的快速排序实现与优化

本教程详细介绍了如何在java中为自定义对象列表实现高效的快速排序算法。我们将重点探讨comparable接口中compareto方法的正确实现，以及快速排序核心的partition（分区）策略。通过分析常见错误并提供优化后的代码示例，帮助开发者理解并掌握快速排序在实际应用中的技巧和注意事项。

快速排序算法概述

快速排序（QuickSort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序的平均时间复杂度为O(n log n)，在大多数实际应用中表现出色。

自定义对象与Comparable接口

在Java中对自定义对象进行排序时，需要让对象实现Comparable接口，并重写其compareTo方法。compareTo方法定义了对象之间进行比较的规则，这是排序算法能够正确工作的关键。

Location类结构

我们以一个Location类为例，该类包含邮政编码（zipCode）、城市（city）、经纬度等信息。我们将根据zipCode进行排序。

public class Location implements Comparable {

    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 String toString() {
        return "Location{" +
               "zipCode='" + zipCode + '\'' +
               ", city='" + city + '\'' +
               '}';
    }

    // compareTo 方法将在下一节详细讨论和修正
    @Override
    public int compareTo(Location o) {
        // 修正后的 compareTo 实现
        // 将 zipCode 字符串转换为整数进行比较
        int thisZip = Integer.parseInt(this.zipCode);
        int otherZip = Integer.parseInt(o.getZipCode());

        return Integer.compare(thisZip, otherZip); // 推荐使用 Integer.compare
    }
}

compareTo方法的正确实现

Comparable接口的compareTo方法约定：

  • 如果当前对象（this）小于指定对象（o），返回负整数。
  • 如果当前对象等于指定对象，返回零。
  • 如果当前对象大于指定对象，返回正整数。

原始代码中的compareTo方法存在逻辑错误，它将“大于”返回-1，“小于”返回1，这与Comparable接口的约定相反，且未处理相等情况。

修正后的compareTo方法： 为了确保排序逻辑的正确性，我们将zipCode字符串转换为整数进行比较。最简洁和推荐的方式是使用Integer.compare()方法。

    @Override
    public int compareTo(Location o) {
        int thisZip = Integer.parseInt(this.zipCode);
        int otherZip = Integer.parseInt(o.getZipCode());

        // Integer.compare(x, y) 等价于 (x < y) ? -1 : ((x == y) ? 0 : 1)
        return Integer.compare(thisZip, otherZip);
    }

通过上述修正，Location对象现在可以根据其邮政编码进行正确的比较。

快速排序核心实现

快速排序主要由一个入口方法、一个递归排序方法和一个分区（partition）辅助方法组成。

1. 入口方法 quickSort

这个方法是快速排序的起点，它负责调用递归排序方法，并传入整个列表的初始范围。

public class QuickSortService { // 假设这是一个服务类来封装排序逻辑

    public void quickSort(List locations) {
        if (locations == null || locations.size() <= 1) {
            return; // 列表为空或只有一个元素，无需排序
        }
        quickSortRecursive(locations, 0, locations.size() - 1);
    }

    // ... 其他方法 ...
}

2. 递归排序方法 quickSortRecursive

这是快速排序的递归实现。它首先检查当前子数组的起始索引是否大于结束索引（递归基线条件），如果不是，则调用partition方法进行分区，然后对分区后的左右两个子数组进行递归排序。

    private void quickSortRecursive(List locations, int startIndex, int endIndex) {
        if (startIndex >= endIndex) { // 递归基线条件：子数组只有一个或没有元素
            return;
        }

        // 获取分区点（pivot的最终位置）
        int pivotIndex = partition(locations, startIndex, endIndex);

        // 对左侧子数组进行递归排序
        quickSortRecursive(locations, startIndex, pivotIndex - 1);
        // 对右侧子数组进行递归排序
        quickSortRecursive(locations, pivotIndex + 1, endIndex);
    }

3. 分区（partition）策略

partition方法是快速排序的核心。它的目标是：

  1. 选择一个基准元素（pivot）。
  2. 重新排列子数组中的元素，使得所有小于或等于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边。
  3. 返回基准元素最终所在的位置。

这里我们采用“Lomuto partition scheme”的变种，选择子数组的第一个元素作为基准。

    private int partition(List locations, int startIndex, int endIndex) {
        Location pivot = locations.get(startIndex); // 选择第一个元素作为基准
        int smallerIndex = startIndex; // smallerIndex 跟踪小于基准的元素的右边界

        // 遍历从 startIndex + 1 到 endIndex 的所有元素
        for (int biggerIndex = startIndex + 1; biggerIndex <= endIndex; biggerIndex++) {
            // 如果当前元素小于或等于基准
            if (locations.get(biggerIndex).compareTo(pivot) <= 0) { // 使用修正后的 compareTo
                smallerIndex++; // 扩展小于基准元素的区域
                swapElements(locations, smallerIndex, biggerIndex); // 将当前元素交换到小于基准的区域
            }
        }
        // 最后，将基准元素（最初在 startIndex）与 smallerIndex 处的元素交换
        // 这样基准元素就到了它最终的正确位置
        swapElements(locations, startIndex, smallerIndex);
        return smallerIndex; // 返回基准元素的最终索引
    }

4. 元素交换（swapElements）辅助方法

这是一个简单的辅助方法，用于交换列表中两个指定索引位置的元素。

    private void swapElements(List input, int firstIndex, int secondIndex) {
        Location temp = input.get(firstIndex);
        input.set(firstIndex, input.get(secondIndex));
        input.set(secondIndex, temp);
    }

完整代码示例

将上述所有修正和实现整合，得到一个完整的、可用于对List进行快速排序的Java代码。

import java.util.List;
import java.util.Collections; // 虽然这里不用，但原问题中提到过

// Location.java 文件
class Location implements Comparable {

    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 String toString() {
        return "Location{zipCode='" + zipCode + "', city='" + city + "'}";
    }

    @Override
    public int compareTo(Location o) {
        // 将 zipCode 字符串转换为整数进行比较
        int thisZip = Integer.parseInt(this.zipCode);
        int otherZip = Integer.parseInt(o.getZipCode());

        return Integer.compare(thisZip, otherZip);
    }
}

// QuickSortService.java 文件
public class QuickSortService {

    public void quickSort(List locations) {
        if (locations == null || locations.size() <= 1) {
            return;
        }
        quickSortRecursive(locations, 0, locations.size() - 1);
    }

    private void quickSortRecursive(List 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);
    }

    private int partition(List locations, int startIndex, int endIndex) {
        Location pivot = locations.get(startIndex); // 选择第一个元素作为基准
        int smallerIndex = startIndex; 

        for (int biggerIndex = startIndex + 1; biggerIndex <= endIndex; biggerIndex++) {
            if (locations.get(biggerIndex).compareTo(pivot) <= 0) { // 使用修正后的 compareTo
                smallerIndex++;
                swapElements(locations, smallerIndex, biggerIndex);
            }
        }
        swapElements(locations, startIndex, smallerIndex);
        return smallerIndex;
    }

    private void swapElements(List input, int firstIndex, int secondIndex) {
        Location temp = input.get(firstIndex);
        input.set(firstIndex, input.get(secondIndex));
        input.set(secondIndex, temp);
    }

    // 示例用法
    public static void main(String[] args) {
        List locations = new java.util.ArrayList<>();
        locations.add(new Location("90210", 34.0, -118.0, "Beverly Hills", "CA"));
        locations.add(new Location("10001", 40.0, -74.0, "New York", "NY"));
        locations.add(new Location("60601", 41.0, -87.0, "Chicago", "IL"));
        locations.add(new Location("90211", 34.1, -118.1, "Beverly Hills", "CA"));
        locations.add(new Location("00001", 10.0, -10.0, "Test City", "TS"));
        locations.add(new Location("60600", 41.0, -87.0, "Chicago", "IL"));

        System.out.println("Original List:");
        locations.forEach(System.out::println);

        QuickSortService sorter = new QuickSortService();
        sorter.quickSort(locations);

        System.out.println("\nSorted List:");
        locations.forEach(System.out::println);
    }
}

快速排序的注意事项与优化

  1. 基准元素（Pivot）的选择：

    • 选择第一个或最后一个元素： 最简单，但在已排序或逆序的数组中会导致最坏情况O(n^2)的性能。
    • 随机选择： 可以有效避免最坏情况，但引入了随机数生成的开销。
    • 三数取中（Median-of-three）： 选择子数组的第一个、中间和最后一个元素的中位数作为基准。这通常是实践中较好的选择，因为它能更好地估计真实中位数，减少出现最坏情况的概率。

  2. 小规模子数组的处理： 当递归到非常小的子数组（例如，元素数量小于10-20个）时，快速排序的递归开销可能超过其效率优势。在这种情况下，切换到插入排序（Insertion Sort）等简单排序算法会更高效。

  3. 最坏情况分析： 如果每次选择的基准元素都使得分区非常不平衡（例如，总是选择最大或最小的元素），快速排序的时间复杂度会退化到O(n^2)。合理选择基准是避免这种情况的关键。

  4. 稳定性： 快速排序通常不是稳定排序算法。这意味着如果列表中存在相等的元素，它们的相对顺序在排序后可能发生改变。如果需要保持相等元素的相对顺序，则需要考虑其他稳定排序算法（如归并排序）。

总结

实现Java中自定义对象的快速排序，关键在于两个方面：

  1. 正确实现Comparable接口的compareTo方法：确保它严格遵循约定，返回负数、零或正数，以正确反映对象之间的比较关系。
  2. 正确实现partition（分区）策略：这是快速排序算法的核心，它负责将列表有效地划分为小于基准和大于基准的两个子集。

通过理解和应用这些原则，并结合适当的优化策略（如改进基准选择、处理小规模子数组），开发者可以构建出高效且健壮的快速排序实现。

广照天下广告 广照天下广告 广照天下广告策划 广照天下广告策划 广照天下 广照天下 广照天下 广照天下 广照天下 广照天下 广照天下广告策划 广照天下广告策划 广照天下广告策划 广照天下广告策划 南昌市广照天下广告策划有限公司 南昌市广照天下广告策划有限公司 南昌市广照天下广告策划有限公司 南昌市广照天下广告策划有限公司

赣ICP备2024031479号