Tôi đang cố gắng chuyển đổi việc triển khai quicksort thành mẫu có thể được sử dụng với các vùng chứa khác bên cạnh vectơ.Làm thế nào để bạn tìm thấy trình vòng lặp ở giữa hai trình lặp?
Ban đầu tôi đã sử dụng các chỉ mục để tìm chỉ mục ở giữa, ví dụ: (first + last)/2. Làm thế nào tôi có thể tìm thấy giữa hai vòng lặp?
std::distance có thể đo khoảng cách giữa hai trình vòng lặp hiệu quả nhất có thể.
std::advance có thể tăng trình lặp một cách hiệu quả nhất có thể.
tôi vẫn không muốn quicksort một danh sách liên kết, mặc dù :)
Tại sao không quicksort một danh sách liên kết? Tìm kiếm ở giữa là không cần thiết cho quicksort ... –
@DietrichEpp: Đúng, nhưng có một lý do mà 'std :: sort' đặc biệt yêu cầu trình vòng lặp truy cập ngẫu nhiên. –
Tôi chắc chắn có một lý do kỹ thuật, nhưng nó không liên quan gì đến thuật toán. Thật dễ dàng để nhanh chóng phân loại danh sách được liên kết. –
Làm thế nào về một cái gì đó như thế này?
bool isMovingFirst = true;
while(first != last) {
if(isMovingFirst) {
++first;
} else {
--last;
}
isMovingFirst = !isMovingFirst;
}
Nó thường được coi là hình thức xấu để reimplement những thứ trong thư viện chuẩn. Đừng lặp lại chính mình và tất cả. – StilesCrisis
Ồ, tôi đồng ý với điều đó hoàn toàn. Tôi chỉ viết nó bởi vì nó hoạt động trong cùng một số bước như khoảng cách (không gọi trước). * Nhưng * sau đó khoảng cách + trước vẫn còn chi phí thấp so với độ phức tạp thời gian O (n log n) của quicksort, vì vậy tôi chắc chắn thấy điểm của bạn là hợp lệ trong trường hợp này. –
Vâng, nếu chúng ta đang đi cho hiệu quả, bạn đã có một bool thêm đi mà bạn không cần ... hãy thử này thay vì: cho (;;) { if (first == last) phá vỡ; ++ trước tiên; if (first == last) break; --Cuối cùng; } – StilesCrisis
Để tìm iterator giữa bạn nên sử dụng:
first + (last - first)/2
Điều này không đúng. Giải pháp của bạn yêu cầu trình vòng lặp truy cập ngẫu nhiên. OP đã yêu cầu một giải pháp độc lập với container. –
BTW, tại sao thực hiện quicksort của riêng bạn? std :: sort nên bao gồm quicksorting, và cũng có stable_sort, partial_sort_copy, vv – StilesCrisis
Tôi đang làm Project Euler và muốn xem xét một số thuật toán sắp xếp, mặc dù nếu tôi định sử dụng lại nó trong tương lai, bạn nói đúng-- Tôi cũng có thể chỉ sử dụng std :: sort. – Louis