Quicksort – Introduction

· Quicksort

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Sắp xếp nhanh, hoặc sắp xếp trao đổi phân vùng, là một thuật toán sắp xếp được phát triển bởi Tony Hoare rằng,

Trong trường hợp trung bình, làm cho O (n log n) so sánh để sắp xếp n số hạng.

Trong trường hợp xấu nhất, nó làm cho O (n2) so sánh, mặc dù hành vi này là rất hiếm.

Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort’s sequential and localized memory references work well with a cache. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.[2]

Sắp xếp nhanh thường nhanh hơn là trong thực tế hơn so với thuật toán khác O(n log n) . [1] Ngoài ra, tài liệu tham khảo bộ nhớ tuần tự và địa phương của Sắp xếp nhanh làm việc tốt với một bộ nhớ cache. Sắp xếp nhanh là một giải thuật so sánh, và trong việc triển khai hiệu quả, không phải là sắp xếp ổn định. Sắp xếp nhanh có thể được thực hiện với một thuật toán phân vùng tại chỗ, ​​vì vậy toàn bộ sắp xếp có thể được thực hiện với chỉ O (log n) không gian thêm được sử dụng bởi các ngăn xếp trong đệ quy. [2]

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: