本教程详细介绍了如何在java中为自定义对象列表实现高效的快速排序算法。文章从`comparable`接口的正确实现入手，逐步深入讲解快速排序的核心原理、分区（partition）操作的实现细节，并提供完整的java代码示例，旨在帮助开发者理解并正确应用这一经典的排序算法，同时指出常见错误及优化策略。
引言：快速排序的重要性
快速排序（QuickSort）是一种高效的、基于比较的排序算法，其平均时间复杂度为O(n log n)，在实际应用中表现出色。它采用“分而治之”的策略，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。理解并正确实现快速排序对于Java开发者来说是一项基本且重要的技能。
准备工作：Location类与Comparable接口
在对自定义对象列表进行排序时，Java要求对象实现Comparable接口，并重写compareTo方法，或者通过Comparator接口提供外部比较器。本教程将以一个Location类为例，演示如何通过Comparable接口进行排序。Location类包含邮政编码（zipCode）、城市（city）等信息，我们将根据邮政编码进行排序。
以下是Location类的定义，其中关键是compareTo方法的实现。
import java.util.Objects; // 导入Objects类用于equals和hashCode 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; } // 推荐重写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); } }
关于compareTo方法的重要说明：
立即学习“Java免费学习笔记（深入）”；
在实现compareTo时，务必遵循Comparable接口的约定。如果this对象在排序上“小于”o对象，应返回负数；“等于”则返回0；“大于”则返回正数。原始问题中的compareTo实现是反向的（this > o返回-1，this
快速排序算法核心原理
快速排序的核心思想可以概括为以下三个步骤：
- 选择基准元素（Pivot Selection）： 从列表中选择一个元素作为“基准”（pivot）。常见的选择包括第一个元素、最后一个元素、中间元素或随机元素。
- 分区（Partitioning）： 重新排列列表，将所有小于基准的元素移到基准的左边，所有大于基准的元素移到基准的右边。等于基准的元素可以放在任意一边。分区结束后，基准元素将位于其最终的排序位置。
- 递归排序（Recursive Sorting）： 对基准元素左右两边的子列表递归地应用快速排序。当子列表只包含一个或零个元素时，递归停止。
分区操作（Partitioning）详解
分区操作是快速排序中最关键的步骤。其目标是：给定一个子列表[startIndex, endIndex]和一个基准元素，将子列表中的元素重新排列，使得基准元素左边的所有元素都小于或等于基准，右边的所有元素都大于或等于基准，并将基准元素放置在其最终的排序位置。
以下是一个常用的分区方案（Lomuto分区方案的变种），它以子列表的第一个元素作为基准。
import java.util.Collections; // 导入Collections类用于swap
// ... Location 类及其他代码 ...
public class QuickSortUtil {
/**
* 公共入口方法，用于对整个列表进行快速排序。
* @param locations 待排序的Location对象列表。
*/
public static void quickSort(List 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 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 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 list, int firstIndex, int secondIndex) {
Location temp = list.get(firstIndex);
list.set(firstIndex, list.get(secondIndex));
list.set(secondIndex, temp);
}
} 分区方法的逻辑解释：
- 我们选择子列表的第一个元素locations.get(startIndex)作为基准pivotValue。
- smallerIndex初始化为startIndex，它将追踪所有小于或等于基准的元素区域的右边界。
- 我们从startIndex + 1开始遍历到endIndex。
- 如果在遍历过程中遇到一个元素locations.get(biggerIndex)，它比pivotValue小（compareTo返回负数），那么：
- 我们将smallerIndex递增1。
- 我们将locations.get(biggerIndex)与locations.get(smallerIndex)交换。这样，smallerIndex左边的所有元素（包括smallerIndex本身）都将小于或等于pivotValue。
- 遍历结束后，smallerIndex指向最后一个小于或等于pivotValue的元素。
- 最后，我们将最初的基准元素（位于startIndex）与locations.get(smallerIndex)交换。这样，基准元素就被放置在了其最终的排序位置上，其左边的所有元素都小于它，右边的所有元素都大于它。
- 返回smallerIndex作为基准元素的最终索引。
完整的快速排序实现
结合上述Location类、compareTo方法和QuickSortUtil类，我们就得到了一个完整的、功能正确的快速排序实现。
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 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
}
} 注意事项与优化
-
基准元素选择策略：
- 固定选择（如第一个或最后一个元素）： 如果输入数据已经部分有序或逆序，这种选择可能导致最坏时间复杂度O(n^2)。
- 随机选择： 每次随机选择一个元素作为基准，可以有效避免最坏情况的发生，使平均性能保持在O(n log n)。
- 三数取中（Median-of-Three）： 选取第一个、中间和最后一个元素的中位数作为基准。这种方法在实践中表现良好，能够进一步减少最坏情况的发生概率。
优化示例（随机选择基准）：
private static int partition(List
locations, int startIndex, int endIndex) { // 随机选择一个索引作为基准，并将其与startIndex处的元素交换 Random random = new Random(); int randomIndex = startIndex + random.nextInt(endIndex - startIndex + 1); swapElements(locations, startIndex, randomIndex); Location pivotValue = locations.get(startIndex); // ... 后续分区逻辑与上面相同 ... } -
小规模子数组优化： 当递归到非常小的子数组时（例如，元素数量小于10-20），快速排序的递归开销可能大于其他简单排序算法（如插入排序）。在这种情况下，可以切换到插入排序，以提高整体性能。
private static void quickSortRecursive(List
locations, int startIndex, int endIndex) { if (startIndex >= endIndex) { return; } // 当子数组大小小于某个阈值时，切换到插入排序 if (endIndex - startIndex + 1 < 10) { // 阈值可根据实际情况调整 insertionSort(locations, startIndex, endIndex); return; } int pivotIndex = partition(locations, startIndex, endIndex); quickSortRecursive(locations, startIndex, pivotIndex - 1); quickSortRecursive(locations, pivotIndex + 1, endIndex); } // 针对子列表的插入排序方法 private static void insertionSort(List locations, int startIndex, int endIndex) { for (int j = startIndex + 1; j <= endIndex; j++) { Location current = locations.get(j); int i = j - 1; // 比较并移动元素 while (i >= startIndex && locations.get(i).compareTo(current) > 0) { locations.set(i + 1, locations.get(i)); i--; } locations.set(i + 1, current); } } -
性能考量：
- 时间复杂度： 平均O(n log n)，最坏O(n^2)。
- 空间复杂度： O(log n)（平均，递归栈深度），最坏O(n)。
稳定性： 快速排序通常是非稳定的排序算法，即相等元素的相对顺序在排序后可能会改变。如果需要保持相等元素的相对顺序，应考虑使用归并排序等稳定排序算法。
总结
本教程详细介绍了Java中快速排序算法的实现，包括自定义对象的Comparable接口设计、核心分区逻辑以及递归排序过程。通过提供清晰的代码示例和详细的解释，我们展示了如何构建一个健壮且高效的快速排序功能。同时，我们探讨了基准选择、小规模子数组优化等提高性能的策略，并强调了compareTo方法正确实现的重要性。掌握快速排序不仅能帮助开发者解决实际的排序问题，还能加深对分治算法和递归思想的理解。
