Arrays.sort() - hai chiến lược khác nhau cho các kiểu dữ liệu nguyên thủy và phức tạp được sắp xếp

Question

Arrays sắp xếp các kiểu dữ liệu nguyên thủy bằng cách sử dụng phương thức DualPivotQuicksort, và các loại phức tạp riêng biệt - sử dụng sắp xếp hợp nhất. (chèn-sắp xếp nếu kích thước đầu vào là nhỏ).

DualPivotQuicksort đang sử dụng sắp xếp hợp nhất vẫn còn trên kích thước đầu vào lớn, tuy nhiên, nó đang sử dụng tính năng kép nhanh trên một loạt các kích thước đầu vào nhỏ hơn.

Điều tôi tự hỏi là-- tại sao sự khác biệt này trong chiến lược phân loại các loại nguyên thủy và không nguyên thủy?

Hiệu suất của thuật toán phụ thuộc đáng kể vào kích thước đầu vào-- không phải loại dữ liệu. Gọi compareTo() thay vì so sánh đồng bằng trên nguyên thủy (>, <, ==) không ghi thêm dung lượng trong bộ nhớ (và do đó không làm chậm hiệu suất thời gian tuyệt đối do bộ nhớ) đáng kể trong thời gian chạy.

Tại sao các phương pháp Arrays.sort() sử dụng các chiến lược sắp xếp khác nhau cho các loại dữ liệu nguyên thủy, và cho các loại dữ liệu phức tạp?

TIA.

Answer 1

Vì sắp xếp loại tham chiếu được đảm bảo là stable, trong khi sắp xếp nguyên thủy không cần (vì vậy nhanh, một thuật toán sắp xếp không ổn định, có thể được sử dụng; sắp xếp hợp nhất mặt khác thực tế là ổn định). Cũng lưu ý rằng quicksort is generally more optimal than mergesort (xem this), điều này giải thích tại sao nó được tận dụng khi phân loại nguyên thủy.

Từ Arrays.sort:

loại này là đảm bảo được ổn định : yếu tố bình đẳng sẽ không được sắp xếp lại như một kết quả của sự phân loại.