Java List快速排序实现详解与优化-java教程-PHP中文网

Java List快速排序实现详解与优化

DDD

发布： 2025-11-10 14:54:23

原创

431人浏览过

java list快速排序实现详解与优化

本文深入探讨了如何在Java中为自定义对象列表实现快速排序算法。我们将从理解`Comparable`接口的正确使用开始，逐步构建一个高效且易于理解的快速排序实现，重点讲解分区（partitioning）策略和递归调用，并提供完整的代码示例及性能优化建议，确保读者能够掌握在实际项目中应用快速排序的能力。

1. 理解 Comparable 接口与对象比较

在对自定义对象列表进行排序时，Java要求这些对象能够相互比较。这通常通过实现 java.lang.Comparable 接口来完成。Comparable 接口定义了一个 compareTo(T o) 方法，该方法根据对象的自然顺序进行比较。

compareTo 方法的约定如下：

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

以下是 Location 类的正确 compareTo 方法实现，它根据 zipCode 字段进行升序排序：

立即学习“Java免费学习笔记（深入）”；

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

    // 省略 getter 方法...

    @Override
    public int compareTo(Location o) {
        // 将邮政编码字符串转换为整数进行比较
        int thisZip = Integer.parseInt(this.zipCode);
        int otherZip = Integer.parseInt(o.getZipCode());
        // 使用 Integer.compare 确保符合 Comparable 接口的约定，实现升序排序
        return Integer.compare(thisZip, otherZip);
    }

    @Override
    public String toString() {
        return "Location{" +
               "zipCode='" + zipCode + '\'' +
               ", city='" + city + '\'' +
               '}';
    }
}

登录后复制

注意事项：

原始的 compareTo 实现逻辑有误，它将大于返回 -1，小于返回 1，这实际上会导致降序排序，并且逻辑不完整。
Integer.parseInt() 可能会抛出 NumberFormatException，在实际应用中，如果 zipCode 不总是有效的数字字符串，需要进行异常处理或数据校验。
Integer.compare(int x, int y) 是 Java 7 引入的静态方法，它比 x > y ? 1 : (x < y ? -1 : 0) 更简洁且不易出错。

2. 快速排序算法概览

快速排序（QuickSort）是一种高效的、基于比较的排序算法，采用分治（Divide and Conquer）策略。其基本思想是：

选择基准（Pivot）： 从列表中选择一个元素作为“基准”。
分区（Partition）： 重新排列列表，将所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。在这个分区结束之后，该基准就处于其最终的排好序的位置上。
递归排序： 递归地对基准左边和右边的子列表进行快速排序。

3. 实现快速排序的核心方法

我们将通过三个辅助方法来实现快速排序：一个用于交换元素，一个用于执行分区操作，以及一个递归排序方法。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

3.1 元素交换辅助方法

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

public static <T> void swapElements(List<T> list, int firstIndex, int secondIndex) {
    T temp = list.get(firstIndex);
    list.set(firstIndex, list.get(secondIndex));
    list.set(secondIndex, temp);
}

登录后复制

3.2 分区（Partition）方法

分区是快速排序中最关键的一步。它的目标是选择一个基准元素，然后重新排列子数组，使得所有小于基准的元素都位于基准的左侧，所有大于基准的元素都位于基准的右侧。最后，返回基准的最终位置。

这里我们采用一种常见的Lomuto分区方案，选择子数组的第一个元素作为基准。

/**
 * 执行分区操作，将列表中的元素根据基准值进行划分。
 *
 * @param list 待排序的列表。
 * @param startIndex 子数组的起始索引。
 * @param endIndex 子数组的结束索引。
 * @return 基准元素最终所在的索引。
 */
private static <T extends Comparable<T>> int partition(List<T> list, int startIndex, int endIndex) {
    T pivotValue = list.get(startIndex); // 选择第一个元素作为基准
    int smallerElementsBoundary = startIndex; // smallerElementsBoundary 跟踪小于基准的元素的右边界

    // 遍历从 startIndex + 1 到 endIndex 的所有元素
    for (int current = startIndex + 1; current <= endIndex; current++) {
        // 如果当前元素小于基准值
        if (list.get(current).compareTo(pivotValue) < 0) {
            smallerElementsBoundary++; // 扩展小于基准元素的区域
            swapElements(list, smallerElementsBoundary, current); // 将当前元素与 smallerElementsBoundary 处的元素交换
        }
    }
    // 循环结束后，所有小于基准的元素都在 startIndex+1 到 smallerElementsBoundary 之间
    // 将基准元素（最初在 startIndex）与 smallerElementsBoundary 处的元素交换
    swapElements(list, startIndex, smallerElementsBoundary);
    return smallerElementsBoundary; // 返回基准元素的最终位置
}

登录后复制

3.3 递归快速排序方法

这是快速排序的递归核心。它根据分区操作返回的基准索引，将列表分为两个子列表，并对它们分别进行递归排序。

/**
 * 快速排序的递归实现。
 *
 * @param list 待排序的列表。
 * @param startIndex 子数组的起始索引。
 * @param endIndex 子数组的结束索引。
 */
private static <T extends Comparable<T>> void quickSortRecursive(List<T> list, int startIndex, int endIndex) {
    // 基本情况：如果子数组只有一个或没有元素，则无需排序
    if (startIndex >= endIndex) {
        return;
    }

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

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

登录后复制

3.4 公共入口方法

为了方便调用，提供一个公共的入口方法来启动快速排序。

/**
 * 对列表进行快速排序的公共入口方法。
 *
 * @param list 待排序的列表。
 */
public static <T extends Comparable<T>> void quickSort(List<T> list) {
    if (list == null || list.size() <= 1) {
        return; // 空列表或单元素列表无需排序
    }
    quickSortRecursive(list, 0, list.size() - 1);
}

登录后复制

4. 完整的快速排序实现示例

将上述所有部分整合到一起，形成一个完整的快速排序工具类。

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class QuickSortUtil {

    /**
     * 对列表进行快速排序的公共入口方法。
     *
     * @param list 待排序的列表。
     */
    public static <T extends Comparable<T>> void quickSort(List<T> list) {
        if (list == null || list.size() <= 1) {
            return; // 空列表或单元素列表无需排序
        }
        quickSortRecursive(list, 0, list.size() - 1);
    }

    /**
     * 快速排序的递归实现。
     *
     * @param list 待排序的列表。
     * @param startIndex 子数组的起始索引。
     * @param endIndex 子数组的结束索引。
     */
    private static <T extends Comparable<T>> void quickSortRecursive(List<T> list, int startIndex, int endIndex) {
        // 基本情况：如果子数组只有一个或没有元素，则无需排序
        if (startIndex >= endIndex) {
            return;
        }

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

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

    /**
     * 执行分区操作，将列表中的元素根据基准值进行划分。
     * 采用Lomuto分区方案，选择第一个元素作为基准。
     *
     * @param list 待排序的列表。
     * @param startIndex 子数组的起始索引。
     * @param endIndex 子数组的结束索引。
     * @return 基准元素最终所在的索引。
     */
    private static <T extends Comparable<T>> int partition(List<T> list, int startIndex, int endIndex) {
        T pivotValue = list.get(startIndex); // 选择第一个元素作为基准
        int smallerElementsBoundary = startIndex; // smallerElementsBoundary 跟踪小于基准的元素的右边界

        // 遍历从 startIndex + 1 到 endIndex 的所有元素
        for (int current = startIndex + 1; current <= endIndex; current++) {
            // 如果当前元素小于基准值
            if (list.get(current).compareTo(pivotValue) < 0) {
                smallerElementsBoundary++; // 扩展小于基准元素的区域
                swapElements(list, smallerElementsBoundary, current); // 将当前元素与 smallerElementsBoundary 处的元素交换
            }
        }
        // 循环结束后，所有小于基准的元素都在 startIndex+1 到 smallerElementsBoundary 之间
        // 将基准元素（

登录后复制

以上就是Java List快速排序实现详解与优化的详细内容，更多请关注php中文网其它相关文章！