本教程详细介绍了如何在java中为自定义对象列表实现高效的快速排序算法。我们将重点探讨comparable接口中compareto方法的正确实现，以及快速排序核心的partition（分区）策略。通过分析常见错误并提供优化后的代码示例，帮助开发者理解并掌握快速排序在实际应用中的技巧和注意事项。
快速排序算法概述
快速排序（QuickSort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序的平均时间复杂度为O(n log n)，在大多数实际应用中表现出色。
自定义对象与Comparable接口
在Java中对自定义对象进行排序时，需要让对象实现Comparable接口，并重写其compareTo方法。compareTo方法定义了对象之间进行比较的规则，这是排序算法能够正确工作的关键。
Location类结构
我们以一个Location类为例，该类包含邮政编码（zipCode）、城市（city）、经纬度等信息。我们将根据zipCode进行排序。
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;
}
@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<Location> locations) {
if (locations == null || locations.size() <= 1) {
return; // 列表为空或只有一个元素，无需排序
}
quickSortRecursive(locations, 0, locations.size() - 1);
}
// ... 其他方法 ...
}2. 递归排序方法 quickSortRecursive
这是快速排序的递归实现。它首先检查当前子数组的起始索引是否大于结束索引（递归基线条件），如果不是，则调用partition方法进行分区，然后对分区后的左右两个子数组进行递归排序。
private void quickSortRecursive(List<Location> 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方法是快速排序的核心。它的目标是：
- 选择一个基准元素（pivot）。
- 重新排列子数组中的元素，使得所有小于或等于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边。
- 返回基准元素最终所在的位置。
这里我们采用“Lomuto partition scheme”的变种，选择子数组的第一个元素作为基准。
private int partition(List<Location> 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<Location> input, int firstIndex, int secondIndex) {
Location temp = input.get(firstIndex);
input.set(firstIndex, input.get(secondIndex));
input.set(secondIndex, temp);
}完整代码示例
将上述所有修正和实现整合，得到一个完整的、可用于对List<Location>进行快速排序的Java代码。
import java.util.List;
import java.util.Collections; // 虽然这里不用，但原问题中提到过
// Location.java 文件
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;
}
@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<Location> locations) {
if (locations == null || locations.size() <= 1) {
return;
}
quickSortRecursive(locations, 0, locations.size() - 1);
}
private 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);
}
private int partition(List<Location> 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<Location> 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<Location> 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（分区）策略：这是快速排序算法的核心，它负责将列表有效地划分为小于基准和大于基准的两个子集。
通过理解和应用这些原则，并结合适当的优化策略（如改进基准选择、处理小规模子数组），开发者可以构建出高效且健壮的快速排序实现。
