本教程详细介绍了如何在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方法约定：
立即学习“Java免费学习笔记（深入）”；
- 如果当前对象（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(Listlocations, 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方法是快速排序的核心。它的目标是：
- 选择一个基准元素（pivot）。
- 重新排列子数组中的元素，使得所有小于或等于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边。
- 返回基准元素最终所在的位置。
这里我们采用“Lomuto partition scheme”的变种，选择子数组的第一个元素作为基准。
private int partition(Listlocations, 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(Listinput, int firstIndex, int secondIndex) { Location temp = input.get(firstIndex); input.set(firstIndex, input.get(secondIndex)); input.set(secondIndex, temp); }
完整代码示例
将上述所有修正和实现整合，得到一个完整的、可用于对List
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); } }
快速排序的注意事项与优化
-
基准元素（Pivot）的选择：
- 选择第一个或最后一个元素： 最简单，但在已排序或逆序的数组中会导致最坏情况O(n^2)的性能。
- 随机选择： 可以有效避免最坏情况，但引入了随机数生成的开销。
- 三数取中（Median-of-three）： 选择子数组的第一个、中间和最后一个元素的中位数作为基准。这通常是实践中较好的选择，因为它能更好地估计真实中位数，减少出现最坏情况的概率。
小规模子数组的处理： 当递归到非常小的子数组（例如，元素数量小于10-20个）时，快速排序的递归开销可能超过其效率优势。在这种情况下，切换到插入排序（Insertion Sort）等简单排序算法会更高效。
最坏情况分析： 如果每次选择的基准元素都使得分区非常不平衡（例如，总是选择最大或最小的元素），快速排序的时间复杂度会退化到O(n^2)。合理选择基准是避免这种情况的关键。
稳定性： 快速排序通常不是稳定排序算法。这意味着如果列表中存在相等的元素，它们的相对顺序在排序后可能发生改变。如果需要保持相等元素的相对顺序，则需要考虑其他稳定排序算法（如归并排序）。
总结
实现Java中自定义对象的快速排序，关键在于两个方面：
- 正确实现Comparable接口的compareTo方法：确保它严格遵循约定，返回负数、零或正数，以正确反映对象之间的比较关系。
- 正确实现partition（分区）策略：这是快速排序算法的核心，它负责将列表有效地划分为小于基准和大于基准的两个子集。
通过理解和应用这些原则，并结合适当的优化策略（如改进基准选择、处理小规模子数组），开发者可以构建出高效且健壮的快速排序实现。
