Theo Wikipedia:Tại sao merge sort được sử dụng bởi java để sắp xếp một mảng lớn hơn yếu tố 7
"Trong Java, Arrays.sort() phương pháp sử dụng merge sort hoặc điều chỉnh quicksort tùy thuộc vào các kiểu dữ liệu và để thực hiện hiệu quả chuyển sang sắp xếp chèn khi ít hơn bảy phần tử mảng là đang được sắp xếp "
Nhưng tại sao? Cả hai sắp xếp hợp nhất và sắp xếp nhanh là O (n log n).
Không phải là quảng cáo đặc biệt:
Phương pháp sắp xếp của Arrava sử dụng quicksort cho mảng nguyên thủy và sắp xếp hợp nhất cho mảng đối tượng.
Why does Java's Arrays.sort method use two different sorting algorithms for different types?
Ngoài ra, theo các tài liệu:
Ví dụ, các thuật toán được sử dụng bởi loại (Object []) không phải là một mergesort, nhưng nó phải được ổn định .
Và một trích dẫn từ javadoc:
loại này là đảm bảo được ổn định: các 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.
lưu ýthực hiện: thực hiện Đây là một ổn định, thích nghi, mergesort lặp đi lặp lại mà đòi hỏi rất ít hơn n lg so sánh (n) khi mảng đầu vào được sắp xếp một phần, trong khi cung cấp các hiệu suất của một mergesort truyền thống khi đầu vào mảng là được sắp xếp ngẫu nhiên. Nếu mảng đầu vào gần như được sắp xếp, việc thực hiện yêu cầu xấp xỉ n so sánh. Lưu trữ tạm thời yêu cầu thay đổi từ một hằng số nhỏ cho các mảng đầu vào được sắp xếp gần như đến tham chiếu đối tượng n/2 cho các mảng đầu vào được sắp xếp ngẫu nhiên.
Việc triển khai có lợi thế bằng nhau tăng dần và giảm dần thứ tự trong mảng đầu vào và có thể tận dụng tăng dần và thứ tự giảm dần trong các phần khác nhau của cùng một mảng đầu vào. Đó là rất phù hợp để hợp nhất hai hoặc nhiều mảng được sắp xếp: chỉ cần ghép nối mảng và sắp xếp mảng kết quả.
Việc triển khai đã được điều chỉnh theo loại danh sách của Tim Peters cho Python (TimSort).
tôi đã nhầm lẫn khi thấy chỉnh sửa, tôi có nghĩa là sắp xếp nhanh chóng. – joker
Họ đã chuyển sang sắp xếp hợp nhất đã điều chỉnh vì thấy rằng thống kê cho bộ dữ liệu được phân loại một phần thực tế phương pháp này có thể nhanh hơn một chút so với sắp xếp nhanh.
Java không bao giờ sử dụng MergeSort cho nguyên thủy, và không bao giờ sử dụng QuickSort cho các kiểu tham chiếu. –
Họ là ai? Xin vui lòng tham khảo. –
Tham khảo: http://docs.oracle.com/javase/tutorial/collections/algorithms/ – AlexR
Trường hợp các thuật toán khác nhau là trường hợp điển hình của hành vi và đây là nơi sắp xếp chèn là một trong những điều tồi tệ nhất. Mặt khác, đối với các bộ sưu tập rất nhỏ (n ≈ n) tính đơn giản của tính năng chèn sẽ thắng.
Quy tắc lựa chọn thuật toán của Java thích QuickSort trước tiên và chỉ quay trở lại một điều gì đó khác do các hạn chế cụ thể. QuickSort, cụ thể là, là một loại không ổn định và do đó chỉ chấp nhận được đối với việc phân loại nguyên thủy. Đối với các kiểu tham chiếu, TimSort được sử dụng như OpenJDK 7 (trước đây là MergeSort).
tôi đã phạm sai lầm tôi có nghĩa là sắp xếp nhanh chóng, xem chỉnh sửa. – joker
Lưu ý bổ sung: Sắp xếp chèn thắng dựa trên các bộ sưu tập nhỏ vì nó có yếu tố không đổi thấp hơn, mà big-O không ghi. Lưu ý rằng, ví dụ: 'n^2 <10n' cho' n <10'. – Dukeling
@Dukeling Vâng, đó là quan điểm của tôi. Tính đơn giản có nghĩa là yếu tố không đổi thấp. –
Quicksort và mergesort đều là O (n log n) trong hiệu suất trung bình. Trong trường hợp xấu nhất, quicksort là O (n^2).
Trường hợp trung bình của họ không phải là O (n^2) ,, O của nó (nlogn). –
Cảm ơn bạn đã đánh bắt điều đó. Tôi đã tập trung vào trường hợp xấu nhất n^2, và gõ nó vô tình cho trung bình. –
Vâng Java 7 sử dụng Timsort - lai ghép hợp nhất và chèn. Như một vấn đề của thực tế nó được sử dụng rộng rãi - android, Octave, python sử dụng nó quá. http://en.wikipedia.org/wiki/Timsort
http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types –
Tôi biết Yannis sẽ xuất hiện và smack tôi cho điều này, nhưng điều này có lẽ nên được trên lập trình viên. – MikeTheLiar
Và đây là câu trả lời của tác giả của mã http://stackoverflow.com/questions/15154158/why-collections-sort-is-using-merge-sort-insteadof-quicksort –