Có std :: sort triển khai Quicksort?

Question

thể trùng lặp:
which type of sorting is used in the function sort()?

Liệu std :: sort thực hiện Sắp xếp nhanh?

Answer 1

Tôi nghĩ vậy. std :: list có một phương thức sắp xếp, hoặc bạn có thể gọi sắp xếp từ đó mất 2 vòng lặp, bắt đầu và kết thúc.

Answer 2

Điều đó tùy thuộc vào việc triển khai thư viện. Việc triển khai merg hợp là phổ biến nhất, vì nó là trường hợp xấu nhất O (N * logN) trong khi quicksort có thể làm suy giảm thành O (N^2).

This xác nhận. Ngoài ra, theo như tôi biết, một số loại heuristic được sử dụng trên đầu vào để quyết định thuật toán nào là tốt nhất để sử dụng nội bộ để các cuộc gọi khác nhau đến std::sort() có thể sử dụng các thuật toán khác nhau.

Answer 3

Từ Wikipedia -

Thuật toán phân loại cụ thể không được ủy quyền và có thể thay đổi trong quá trình triển khai. Sort Wiki Link

Answer 4

Nó sử dụng quicksort hoặc introsort.

http://www.sgi.com/tech/stl/sort.html

Answer 5

vì sự phức tạp cao tồi tệ nhất của quicksort (N^2) và tương đối khó khăn để thực hiện trên LINKLIST. Tôi nghĩ rằng sẽ không được thực hiện bằng cách sử dụng quicksort

Answer 6

Có hai thuật toán được sử dụng theo truyền thống.

std::sort là nhiều khả năng sử dụng QuickSort, hoặc ít nhất là một biến thể hơn Sắp xếp nhanh gọi IntroSort, mà "thoái hóa" để HeapSort khi đệ quy đi quá sâu.

Từ tiêu chuẩn:

phức tạp: O (N log (N)) so sánh.

std::stable_sort rất có thể sử dụng MergeSort, vì yêu cầu về độ ổn định. Tuy nhiên lưu ý rằng MergeSort yêu cầu thêm không gian để có hiệu quả.

Từ tiêu chuẩn:

phức tạp: Nó ở N nhất đăng nhập (N) so sánh; nếu có đủ bộ nhớ bổ sung, nó là N log (N).

Tôi chưa thấy một std::sort thực hiện TimSort đó là đầy hứa hẹn và đã được áp dụng trong Python (thủ công cho nó trong thực tế), Java và Android (cho đến nay).