Java: sắp xếp một ArrayList tại chỗ

Question

Trong thư viện chuẩn của Java, có phương pháp nào có thể cho phép một sắp xếp một ArrayList tại chỗ, tức là sử dụng bộ nhớ bổ sung O(1) không?

Collections.sort(List<T>) không đáp ứng yêu cầu này vì nó

bãi danh mục quy định vào một mảng, sắp xếp mảng, và lặp trên danh sách đặt lại mỗi phần tử từ vị trí tương ứng trong mảng.

Nếu không có gì trong thư viện chuẩn, thư viện của bên thứ ba nào có thể được sử dụng để thực hiện việc này?

Answer 1

Bạn có thể trích xuất mảng cơ bản (ví dụ: phản chiếu) và thực hiện một Arrays.sort (mảng, 0, list.size()) trên đó.

Java 7 không sao chép mảng trong Arrays.sort() trước khi sắp xếp mảng. Trong Java 6 nó có nghĩa là Collections.sort() trong Java 6 thực sự sao chép mảng cơ bản TWICE để thực hiện sắp xếp.

Answer 2

Đơn giản, không. Collections.sort() được tạo ra để phân loại, có vẻ như bạn phải tự thực hiện. Đối với danh sách tôi sẽ sử dụng Bubblesort, bởi vì nó chỉ trao đổi hai yếu tố hàng xóm, có thể được thực hiện rất đơn giản mà không thay đổi các thùng.

Answer 3

Collections.sort() được tạo để làm việc với bất kỳ triển khai Danh sách nào, và đó là lý do tại sao nó không hoạt động tại chỗ (sáp nhập LinkedList tại chỗ là khó khăn và hy sinh sự ổn định).

Nếu bạn thực sự lo lắng về việc sắp xếp tại chỗ, bạn sẽ phải triển khai tính năng sắp xếp của riêng mình. Nó không thực sự đáng giá thời gian của bạn trừ khi Danh sách của bạn rất dài.

Arrays.sort(Object[]) hiện mergesort cùng và được gọi trong nội bộ bởi Collections.sort() (ít nhất là trong openjdk)