Chúng ta có thể nhanh chóng sắp xếp với độ phức tạp của trường hợp xấu nhất?

Question

Tôi đã tự hỏi nếu chúng ta bằng cách nào đó có thể sửa đổi thuật toán sắp xếp nhanh để tạo ra sự phức tạp thời gian trường hợp xấu nhất của O (n logn). Mặc dù điều này có thể được thực hiện bằng cách hoán đổi dữ liệu và sau đó giả định rằng chúng ta sẽ nhận được sự phức tạp của trường hợp trung bình hơn là trường hợp xấu nhất. Nhưng đây không phải là một giải pháp chứng minh đầy đủ vì chúng ta có thể một lần nữa rơi vào trường hợp xấu nhất sau khi hoán đổi. Có cách nào khác xung quanh mà bạn có thể đề nghị.

Answer 1

Vâng, vâng, chúng tôi có thể đưa nó xuống O (nlogn). Tất cả các thuật toán tôi đã thấy rằng cố gắng để đưa ra điều này được dựa trên lựa chọn điểm pivot của bạn. Nếu bạn có thể "thông minh" chọn điểm xoay của bạn, nó có thể được đưa xuống.

Tùy chọn 1. Intro Sort. Nó bây giờ không còn là một "nhanh" tinh khiết. Nó sử dụng sắp xếp hợp nhất sau này. 2. Chọn trung vị làm trục xoay. Bây giờ việc tìm kiếm trung bình có thể mất rất nhiều thời gian nếu được thực hiện theo cách thông thường NHƯNG có đề cập đến trong số Introduction to Algorithms.

Dưới đây là một cái gì đó trực tiếp từ miệng của ngựa Introduction to Algorithms

1. Divide mảng vào [n/5] nhóm với mỗi nhóm có 5 yếu tố
2. Tìm trung bình của mỗi nhóm sử dụng chèn sắp xếp và sau đó chọn trung bình từ danh sách này
3. Sau đó, bạn cần phải thử đệ quy và tìm trung bình [n/5] số trung vị được tính từ mỗi nhóm.
4. phân vùng các mảng xung quanh trung bình

này Có một số công cụ phức tạp hơn trong thuật toán này mà tôi đã ẩn. Bạn có thể đi qua nó trong cùng một cuốn sách nếu bạn muốn. Thông thường, tôi không cố gắng sử dụng thuật toán này. Tôi sử dụng một phép chọn ngẫu nhiên để tìm trục xoay và làm việc với nó.

Answer 2

Vâng "sửa đổi" là một từ khá chủ quan ở đây. Có một số cách bạn có thể tăng nhanh để làm cho nó chạy trong O(n log n). Có hay không bạn vẫn có thể gọi nó là một loại nhanh chóng được xác định.

Một trong số đó là introsort. Introsort bắt đầu với quicksort nhưng sau đó chuyển sang hợp nhất sắp xếp có trường hợp phức tạp tồi tệ nhất O(n log n). Một trong những mục đích của introsort là để chống lại danh sách kẻ giết người trung bình-of-3.