Sắp xếp trong Java

Hai bài trước tự viết thuật toán sắp xếp để hiểu bên trong. Khi đi làm, bạn gần như luôn dùng method có sẵn của Java vì nhanh, đã được kiểm thử kỹ và gọn. Điều cần biết là nên chọn method nào, và method nào đổi luôn list gốc.

Khái niệm

⚖️ Sắp xếp ổn định (stable sort): các phần tử bằng nhau theo tiêu chí sắp xếp vẫn giữ đúng thứ tự ban đầu của chúng.

Tất cả đều O(n log n). sorted đã gặp ở bài Stream cơ bản của khoá Java Core.

Ví dụ

// Main.java
void main() {
    List<Product> products = new ArrayList<>(List.of(
        new Product("Vở", 12000),
        new Product("Bút bi", 5000),
        new Product("Thước", 7000)));

    products.sort((a, b) ->
        Long.compare(a.getPrice(), b.getPrice()));
    for (Product p : products) {
        System.out.println("%s: %d".formatted(
            p.getName(), p.getPrice()));
    }
}

// Product.java
class Product {
    private String name;
    private long price;

    public Product(String name, long price) {
        this.name = name;
        this.price = price;
    }

    public String getName() { return name; }
    public long getPrice() { return price; }
}

• sort nhận lambda so hai phần tử a, b. Kết quả âm nghĩa là a đứng trước, dương là b đứng trước, 0 là bằng nhau.
• Long.compare(a.getPrice(), b.getPrice()) trả về đúng số âm, 0 hoặc dương như vậy.
• Muốn giảm dần thì đổi chỗ: Long.compare(b.getPrice(), a.getPrice()).
• sort đổi thứ tự ngay trong products, in ra Bút bi, Thước, Vở. List tạo bằng List.of không sửa được, nên được bọc trong new ArrayList<>(...).

Thử ngay

Hai món cùng giá 5000. Giữ Product.java, thay Main.java bằng đoạn dưới và xem món nào đứng trước:

// Main.java
void main() {
    List<Product> items = new ArrayList<>(List.of(
        new Product("Vở", 12000),
        new Product("Bút chì", 5000),
        new Product("Thước", 7000),
        new Product("Bút bi", 5000)));

    items.sort(Comparator.comparingLong(
        p -> p.getPrice()));
    for (Product p : items) {
        System.out.println("%s: %d".formatted(
            p.getName(), p.getPrice()));
    }
}

Đoán trước khi chạy: "Bút chì" và "Bút bi" cùng giá. Món nào in ra trước?

Bút chì: 5000
Bút bi: 5000
Thước: 7000
Vở: 12000

Lỗi hay gặp

Gọi stream().sorted(...) rồi tưởng list đã đổi. sorted trả về kết quả mới, list gốc giữ nguyên. Không dùng kết quả trả về thì coi như chưa sắp xếp.

// SAI — items vẫn giữ thứ tự lúc tạo
items.stream()
    .sorted(Comparator.comparingLong(p -> p.getPrice()))
    .toList();
System.out.println(items.get(0).getName());   // Vở

// ĐÚNG — dùng list mà toList() trả về
List<Product> sorted = items.stream()
    .sorted(Comparator.comparingLong(p -> p.getPrice()))
    .toList();
System.out.println(sorted.get(0).getName());
// Bút chì

Tóm tắt

• list.sort và Collections.sort sắp xếp tại chỗ, O(n log n), ổn định.
• stream().sorted(...) trả về kết quả mới, cũng ổn định.
• Lambda so sánh trả số âm, 0 hoặc dương. Long.compare và Comparator.comparingLong làm sẵn việc đó.
• list.sort của Java là TimSort: kết hợp merge sort với sắp xếp chèn cho đoạn ngắn.