如何用mergeSort将Book类型ArrayList按书名排序为Item集合并实现二分查找方法

嘿，我来帮你一步步搞定这个需求！咱们分模块来，先搞定归并排序转成有序的Item列表，再实现二分查找的方法。

首先得确认Book是Item的子类（或者Item是包含Title、Author、ID的父类），这样我们才能把Book对象安全转成Item类型。举个简单的类结构例子：

class Item {
    protected String title;
    protected String author;
    protected int id;

    // 构造器、getter/setter方法
    public String getTitle() {
        return title;
    }
}

class Book extends Item {
    // 可以加Book专属的属性或方法，比如ISBN之类的
}

首先咱们先把存储Book的ArrayList转成Item类型的列表——如果Book是Item子类的话，直接转就行：

ArrayList<Book> bookList = new ArrayList<>();
// 假设你已经给bookList塞了一堆Book对象
ArrayList<Item> itemList = new ArrayList<>(bookList); // 向上转型，直接搞定类型转换

接下来实现归并排序，核心是分治法+按书名比较。咱们写个工具类来封装排序逻辑，方便复用：

public class BookSortSearchHelper {
    // 归并排序主方法，直接传入要排序的Item列表
    public static void mergeSort(ArrayList<Item> list) {
        if (list.size() <= 1) {
            return; // 只有一个元素或者空列表，不用排
        }

        // 把列表拆成左右两半
        int mid = list.size() / 2;
        ArrayList<Item> leftHalf = new ArrayList<>(list.subList(0, mid));
        ArrayList<Item> rightHalf = new ArrayList<>(list.subList(mid, list.size()));

        // 递归排序左右两个子列表
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        // 把两个有序的子列表合并成一个有序列表
        merge(list, leftHalf, rightHalf);
    }

    // 合并逻辑，按书名字母顺序排序
    private static void merge(ArrayList<Item> resultList, ArrayList<Item> left, ArrayList<Item> right) {
        int leftIdx = 0, rightIdx = 0, resultIdx = 0;

        // 逐个比较左右列表的元素，把小的（字母顺序靠前的）放进结果列表
        while (leftIdx < left.size() && rightIdx < right.size()) {
            // 这里用compareTo做自然排序，要是想忽略大小写就换成compareToIgnoreCase
            if (left.get(leftIdx).getTitle().compareTo(right.get(rightIdx).getTitle()) <= 0) {
                resultList.set(resultIdx++, left.get(leftIdx++));
            } else {
                resultList.set(resultIdx++, right.get(rightIdx++));
            }
        }

        // 把左右列表剩下的元素补进去
        while (leftIdx < left.size()) {
            resultList.set(resultIdx++, left.get(leftIdx++));
        }
        while (rightIdx < right.size()) {
            resultList.set(resultIdx++, right.get(rightIdx++));
        }
    }
}

调用的时候就一行代码：

BookSortSearchHelper.mergeSort(itemList);

搞定！现在itemList就是按书名字母顺序排好的Item列表了。

二分查找的前提是列表已经有序，刚好咱们已经用归并排序搞定了。这个方法接收用户输入的书名，在有序列表里找，找到就返回对应的Item（你可以在这之后加后续操作），没找到就返回null。

直接在刚才的工具类里加这个方法：

public static Item searchTitle(ArrayList<Item> sortedItemList, String targetTitle) {
    int left = 0;
    int right = sortedItemList.size() - 1;

    while (left <= right) {
        // 计算中间索引，这么写是为了避免整数溢出
        int mid = left + (right - left) / 2;
        Item midItem = sortedItemList.get(mid);
        int compareResult = midItem.getTitle().compareTo(targetTitle);

        if (compareResult == 0) {
            // 找到啦！返回这个Item，你可以在这里直接写后续操作
            return midItem;
        } else if (compareResult < 0) {
            // 目标书名在右半部分，调整左边界
            left = mid + 1;
        } else {
            // 目标书名在左半部分，调整右边界
            right = mid - 1;
        }
    }
    // 循环结束还没找到，返回null
    return null;
}

调用示例 #

比如用户输入了一个书名，咱们这么用：

// 假设已经有排好序的sortedItemList
String userInput = "1984"; // 模拟用户输入的书名
Item foundBook = BookSortSearchHelper.searchTitle(sortedItemList, userInput);

if (foundBook != null) {
    // 这里写你的后续操作，比如打印书籍信息
    System.out.println("找到啦！书名：" + foundBook.getTitle() + "，作者：" + foundBook.author);
} else {
    System.out.println("抱歉，没找到这个书名的书籍");
}

• 如果Book不是Item的子类，那你得手动把Book的属性复制到Item对象里，比如：

ArrayList<Item> itemList = new ArrayList<>();
for (Book book : bookList) {
    Item item = new Item();
    item.setTitle(book.getTitle());
    item.setAuthor(book.getAuthor());
    item.setId(book.getId());
    itemList.add(item);
}

• 要是想忽略大小写查找，把compareTo换成compareToIgnoreCase就行，这样用户输入大写小写都能找到。
• 归并排序是稳定排序，时间复杂度O(n log n)，大数据量下也很高效；二分查找是O(log n)，比挨个找快多了。

内容的提问来源于stack exchange，提问作者Chase Allen