Làm thế nào để triển khai các thuật toán sắp xếp cổ điển trong C ++ hiện đại?

331
TemplateRex 2014-07-09 23:59.

Các std::sortthuật toán (và anh em họ của mình std::partial_sortstd::nth_element) từ Thư viện chuẩn C ++ là trong hầu hết các trường một sự pha trộn phức tạp và hybrid của các thuật toán sắp xếp cơ bản hơn , chẳng hạn như sắp xếp chọn, sắp xếp chèn, nhanh chóng sắp xếp, sắp xếp hợp nhất, hoặc loại heap.

Có rất nhiều câu hỏi ở đây và trên các trang web chị em như https://codereview.stackexchange.com/ liên quan đến lỗi, độ phức tạp và các khía cạnh khác của việc triển khai các thuật toán sắp xếp cổ điển này. Hầu hết các triển khai được cung cấp bao gồm các vòng lặp thô, sử dụng thao tác lập chỉ mục và các loại cụ thể, và nói chung là không tầm thường để phân tích về tính đúng đắn và hiệu quả.

Câu hỏi : Làm thế nào để các thuật toán sắp xếp cổ điển được đề cập ở trên có thể được thực hiện bằng cách sử dụng C ++ hiện đại?

  • không có vòng lặp thô , nhưng kết hợp các khối xây dựng thuật toán của Thư viện Chuẩn từ<algorithm>
  • giao diện trình lặp và sử dụng các mẫu thay vì thao tác lập chỉ mục và các loại cụ thể
  • Kiểu C ++ 14 , bao gồm Thư viện chuẩn đầy đủ, cũng như các bộ giảm nhiễu cú pháp như autobí danh mẫu, bộ so sánh trong suốt và lambdas đa hình.

Ghi chú :

  • để tham khảo thêm về cách triển khai các thuật toán sắp xếp, hãy xem Wikipedia , Mã Rosetta hoặc http://www.sorting-algorithm.com/
  • theo quy ước của Sean Parent (trang trình bày 39), một vòng lặp thô là một for-loop dài hơn so với hợp phần của hai hàm với một toán tử. Vì vậy f(g(x));, f(x); g(x);hoặc f(x) + g(x);không phải là các vòng lặp thô, và cũng không phải là các vòng lặp trong selection_sortinsertion_sortdưới.
  • Tôi làm theo thuật ngữ của Scott Meyers để biểu thị C ++ 1y hiện tại đã là C ++ 14 và để biểu thị C ++ 98 và C ++ 03 cả hai đều là C ++ 98, vì vậy đừng kích động tôi vì điều đó.
  • Như được đề xuất trong phần nhận xét của @Mehrdad, tôi cung cấp bốn cách triển khai làm Ví dụ trực tiếp ở cuối câu trả lời: C ++ 14, C ++ 11, C ++ 98 và Boost và C ++ 98.
  • Bản thân câu trả lời chỉ được trình bày dưới dạng C ++ 14. Nếu có liên quan, tôi biểu thị sự khác biệt về cú pháp và thư viện nơi các phiên bản ngôn ngữ khác nhau khác nhau.

2 answers

392
TemplateRex 2014-07-09 23:59.

Các khối xây dựng thuật toán

Chúng tôi bắt đầu bằng cách lắp ráp các khối xây dựng thuật toán từ Thư viện chuẩn:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // distance, begin, end, next
  • các công cụ vòng lặp như không phải thành viên std::begin()/ std::end()cũng như với std::next()chỉ có sẵn từ C ++ 11 trở lên. Đối với C ++ 98, người ta cần phải tự viết chúng. Có những sản phẩm thay thế từ Boost.Range in boost::begin()/ boost::end()và từ Boost.Utility in boost::next().
  • các std::is_sortedthuật toán chỉ có sẵn cho C ++ 11 và xa hơn nữa. Đối với C ++ 98, điều này có thể được thực hiện trong điều kiện std::adjacent_findvà một đối tượng hàm viết tay. Boost.Algorithm cũng cung cấp một boost::algorithm::is_sortedsự thay thế.
  • các std::is_heapthuật toán chỉ có sẵn cho C ++ 11 và xa hơn nữa.

Tính năng tổng hợp

C ++ 14 cung cấp các trình so sánh minh bạch của biểu mẫu std::less<>hoạt động đa hình trên các đối số của chúng. Điều này tránh phải cung cấp kiểu của trình lặp. Điều này có thể được sử dụng kết hợp với các đối số mẫu hàm mặc định của C ++ 11 để tạo một quá tải duy nhất cho các thuật toán sắp xếp lấy <làm so sánh và các thuật toán có đối tượng hàm so sánh do người dùng xác định.

template<class It, class Compare = std::less<>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

Trong C ++ 11, người ta có thể xác định bí danh mẫu có thể sử dụng lại để trích xuất kiểu giá trị của trình vòng lặp, điều này làm tăng thêm sự lộn xộn nhỏ cho chữ ký của thuật toán sắp xếp:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

template<class It, class Compare = std::less<value_type_t<It>>>
void xxx_sort(It first, It last, Compare cmp = Compare{});

Trong C ++ 98, người ta cần viết hai quá tải và sử dụng typename xxx<yyy>::typecú pháp dài dòng

template<class It, class Compare>
void xxx_sort(It first, It last, Compare cmp); // general implementation

template<class It>
void xxx_sort(It first, It last)
{
    xxx_sort(first, last, std::less<typename std::iterator_traits<It>::value_type>());
}
  • Một điểm tốt về cú pháp khác là C ++ 14 tạo điều kiện cho việc gói các trình so sánh do người dùng xác định thông qua lambdas đa hình (với autocác tham số được suy ra giống như các đối số của mẫu hàm).
  • C ++ 11 chỉ có lambdas đơn hình, yêu cầu sử dụng bí danh mẫu ở trên value_type_t.
  • Trong C ++ 98, người ta cần viết một đối tượng hàm độc lập hoặc sử dụng kiểu cú pháp dài dòng std::bind1st/ std::bind2nd/ std::not1.
  • Boost.Bind cải thiện điều này với cú pháp boost::bind_1/ _2placeholder.
  • C ++ 11 và hơn thế nữa cũng có std::find_if_not, trong khi C ++ 98 cần std::find_ifvới một std::not1đối tượng hàm xung quanh.

Kiểu C ++

Không có kiểu C ++ 14 nào được chấp nhận chung. Để tốt hơn hay tệ hơn, tôi theo dõi chặt chẽ bản thảo C ++ hiện đại hiệu quả của Scott Meyers và GotW cải tiến của Herb Sutter . Tôi sử dụng các đề xuất phong cách sau:

  • Đề xuất "Hầu như luôn luôn tự động" của Herb Sutter và "Ưu tiên tự động khai báo loại cụ thể" của Scott Meyers , về độ ngắn gọn là vượt trội, mặc dù sự rõ ràng của nó đôi khi bị tranh cãi .
  • "Phân biệt (){}khi tạo đối tượng" của Scott Meyers và nhất quán chọn khởi tạo {}dấu ngoặc đơn thay vì khởi tạo dấu ngoặc đơn cũ ()(để loại bỏ tất cả các vấn đề khó phân tích cú pháp nhất trong mã chung).
  • "Ưu tiên khai báo bí danh cho typedefs" của Scott Meyers . Đối với các mẫu, đây là điều bắt buộc và sử dụng nó ở mọi nơi thay vì typedeftiết kiệm thời gian và thêm tính nhất quán.
  • Tôi sử dụng một for (auto it = first; it != last; ++it)mẫu ở một số nơi, để cho phép kiểm tra sự bất biến của vòng lặp cho các phạm vi con đã được sắp xếp. Trong mã sản xuất, việc sử dụng while (first != last)và một ++firstnơi nào đó bên trong vòng lặp có thể tốt hơn một chút.

Sắp xếp lựa chọn

Sắp xếp lựa chọn không thích ứng với dữ liệu theo bất kỳ cách nào, vì vậy thời gian chạy của nó luôn luônO(N²). Tuy nhiên, sắp xếp lựa chọn có đặc tính là giảm thiểu số lần hoán đổi . Trong các ứng dụng có chi phí hoán đổi các mục cao, sắp xếp lựa chọn rất tốt có thể là thuật toán lựa chọn.

Để triển khai nó bằng cách sử dụng Thư viện chuẩn, hãy sử dụng nhiều lần std::min_elementđể tìm phần tử tối thiểu còn lại và iter_swaphoán đổi nó vào vị trí:

template<class FwdIt, class Compare = std::less<>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Lưu ý rằng selection_sortphạm vi đã được xử lý được [first, it)sắp xếp là bất biến vòng lặp của nó. Các yêu cầu tối thiểu là các trình vòng lặp chuyển tiếp , so với std::sortcác trình vòng lặp truy cập ngẫu nhiên của.

Chi tiết bị bỏ qua :

  • sắp xếp lựa chọn có thể được tối ưu hóa với thử nghiệm sớm if (std::distance(first, last) <= 1) return;(hoặc cho các trình lặp chuyển tiếp / hai chiều if (first == last || std::next(first) == last) return;:).
  • đối với trình vòng lặp hai chiều , thử nghiệm trên có thể được kết hợp với một vòng lặp trong khoảng thời gian [first, std::prev(last)), vì phần tử cuối cùng được đảm bảo là phần tử còn lại tối thiểu và không yêu cầu hoán đổi.

Sắp xếp chèn

Mặc dù nó là một trong những thuật toán sắp xếp cơ bản với O(N²)thời gian trong trường hợp xấu nhất, sắp xếp chèn là thuật toán được lựa chọn khi dữ liệu gần được sắp xếp (vì nó thích ứng ) hoặc khi kích thước vấn đề nhỏ (vì nó có chi phí thấp). Vì những lý do này và bởi vì nó cũng ổn định , sắp xếp chèn thường được sử dụng làm trường hợp cơ sở đệ quy (khi kích thước vấn đề nhỏ) cho các thuật toán sắp xếp phân chia chi phí cao hơn, chẳng hạn như sắp xếp hợp nhất hoặc sắp xếp nhanh.

Để triển khai insertion_sortvới Thư viện chuẩn, hãy sử dụng nhiều lần std::upper_boundđể tìm vị trí mà phần tử hiện tại cần đến và sử dụng std::rotateđể chuyển các phần tử còn lại lên trên trong phạm vi đầu vào:

template<class FwdIt, class Compare = std::less<>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Lưu ý rằng insertion_sortphạm vi đã được xử lý được [first, it)sắp xếp là bất biến vòng lặp của nó. Sắp xếp chèn cũng hoạt động với các trình vòng lặp chuyển tiếp.

Chi tiết bị bỏ qua :

  • sắp xếp chèn có thể được tối ưu hóa với thử nghiệm sớm if (std::distance(first, last) <= 1) return;(hoặc cho trình vòng lặp chuyển tiếp / hai chiều if (first == last || std::next(first) == last) return;:) và vòng lặp trong khoảng thời gian [std::next(first), last), vì phần tử đầu tiên được đảm bảo ở đúng vị trí và không yêu cầu xoay.
  • đối với trình vòng lặp hai chiều , tìm kiếm nhị phân để tìm điểm chèn có thể được thay thế bằng tìm kiếm tuyến tính ngược sử dụng std::find_if_notthuật toán của Thư viện Chuẩn .

Bốn ví dụ trực tiếp ( C ++ 14 , C ++ 11 , C ++ 98 và Boost , C ++ 98 ) cho phân đoạn dưới đây:

using RevIt = std::reverse_iterator<BiDirIt>;
auto const insertion = std::find_if_not(RevIt(it), RevIt(first), 
    [=](auto const& elem){ return cmp(*it, elem); }
).base();
  • Đối với các đầu vào ngẫu nhiên, điều này cho phép O(N²)so sánh, nhưng điều này cải thiện thành O(N)so sánh cho các đầu vào gần như được sắp xếp. Tìm kiếm nhị phân luôn sử dụng phép O(N log N)so sánh.
  • Đối với các phạm vi đầu vào nhỏ, vị trí bộ nhớ tốt hơn (bộ nhớ đệm, tìm nạp trước) của tìm kiếm tuyến tính cũng có thể chiếm ưu thế trong tìm kiếm nhị phân (tất nhiên, người ta nên kiểm tra điều này).

Sắp xếp nhanh chóng

Khi được triển khai cẩn thận, sắp xếp nhanh sẽ mạnh mẽ và có O(N log N)độ phức tạp dự kiến, nhưng với O(N²)độ phức tạp trong trường hợp xấu nhất có thể được kích hoạt với dữ liệu đầu vào được chọn bất lợi. Khi không cần sắp xếp ổn định, sắp xếp nhanh là một kiểu sắp xếp có mục đích chung tuyệt vời.

Ngay cả đối với các phiên bản đơn giản nhất, sắp xếp nhanh cũng khá phức tạp hơn một chút để triển khai bằng Thư viện chuẩn so với các thuật toán sắp xếp cổ điển khác. Phương pháp bên dưới sử dụng một số tiện ích trình lặp để xác định vị trí phần tử giữa của phạm vi đầu vào [first, last)làm trục xoay, sau đó sử dụng hai lệnh gọi tới std::partition(chính là O(N)) để phân vùng ba chiều phạm vi đầu vào thành các phân đoạn của phần tử nhỏ hơn, bằng, và lớn hơn trục đã chọn, tương ứng. Cuối cùng, hai phân đoạn bên ngoài có các phần tử nhỏ hơn và lớn hơn trục xoay được sắp xếp đệ quy:

template<class FwdIt, class Compare = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = *std::next(first, N / 2);
    auto const middle1 = std::partition(first, last, [=](auto const& elem){ 
        return cmp(elem, pivot); 
    });
    auto const middle2 = std::partition(middle1, last, [=](auto const& elem){ 
        return !cmp(pivot, elem);
    });
    quick_sort(first, middle1, cmp); // assert(std::is_sorted(first, middle1, cmp));
    quick_sort(middle2, last, cmp);  // assert(std::is_sorted(middle2, last, cmp));
}

Tuy nhiên, sắp xếp nhanh là khá khó để có được chính xác và hiệu quả, vì mỗi bước trên phải được kiểm tra cẩn thận và tối ưu hóa cho mã cấp sản xuất. Đặc biệt, đối với O(N log N)độ phức tạp, pivot phải dẫn đến một phân vùng cân bằng của dữ liệu đầu vào, điều này không thể được đảm bảo nói chung cho một O(1)pivot, nhưng có thể được đảm bảo nếu người ta đặt pivot làm giá O(N)trị trung bình của phạm vi đầu vào.

Chi tiết bị bỏ qua :

  • việc triển khai ở trên đặc biệt dễ bị ảnh hưởng bởi các đầu vào đặc biệt, ví dụ như nó có O(N^2)độ phức tạp đối với đầu vào " organ pipe " 1, 2, 3, ..., N/2, ... 3, 2, 1(vì phần giữa luôn lớn hơn tất cả các phần tử khác).
  • lựa chọn xoay vòng trung bình của 3 từ các phần tử được chọn ngẫu nhiên từ phạm vi đầu vào bảo vệ chống lại các đầu vào gần như được sắp xếp mà nếu không độ phức tạp sẽ giảm xuốngO(N^2).
  • Phân vùng 3 chiều (tách các phần tử nhỏ hơn, bằng và lớn hơn pivot) như thể hiện trong hai lệnh gọi tớistd::partitionkhông phải làO(N)thuật toánhiệu quả nhấtđể đạt được kết quả này.
  • đối với các trình vòng lặp truy cập ngẫu nhiên , O(N log N)độ phức tạp được đảm bảo có thể đạt được thông qua lựa chọn trục trung bình bằng cách sử dụng std::nth_element(first, middle, last), theo sau là các lệnh gọi đệ quy đến quick_sort(first, middle, cmp)quick_sort(middle, last, cmp).
  • Tuy nhiên, đảm bảo này phải trả giá vì yếu tố không đổi về O(N)độ phức tạp của std::nth_elementcó thể đắt hơn so với O(1)độ phức tạp của trục trung bình của 3 theo sau bởi một O(N)cuộc gọi đến std::partition(là một chuyển tiếp đơn thân thiện với bộ nhớ cache dữ liệu).

Hợp nhất sắp xếp

Nếu O(N)không quan tâm đến việc sử dụng thêm không gian, thì sắp xếp hợp nhất là một lựa chọn tuyệt vời: nó là thuật toán sắp xếp ổn định duy nhất O(N log N).

Rất đơn giản để triển khai bằng cách sử dụng các thuật toán Tiêu chuẩn: sử dụng một vài tiện ích trình vòng lặp để xác định vị trí giữa phạm vi đầu vào [first, last)và kết hợp hai phân đoạn được sắp xếp đệ quy với std::inplace_merge:

template<class BiDirIt, class Compare = std::less<>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Sắp xếp hợp nhất yêu cầu trình vòng lặp hai chiều, nút cổ chai là std::inplace_merge. Lưu ý rằng khi sắp xếp danh sách được liên kết, sắp xếp hợp nhất chỉ yêu cầu O(log N)thêm không gian (đối với đệ quy). Thuật toán thứ hai được thực hiện std::list<T>::sorttrong Thư viện chuẩn.

Sắp xếp đống

Sắp xếp đống rất đơn giản để thực hiện, thực hiệnO(N log N)sắp xếp tại chỗ, nhưng không ổn định.

Vòng lặp đầu tiên, O(N)giai đoạn "heapify", đặt mảng vào thứ tự đống. Vòng lặp thứ hai, O(N log Ngiai đoạn) "sắp xếp xuống", lặp lại trích xuất tối đa và khôi phục thứ tự đống. Thư viện Chuẩn làm cho điều này cực kỳ đơn giản:

template<class RandomIt, class Compare = std::less<>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    lib::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    lib::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Trong trường hợp bạn coi việc sử dụng là "gian lận" std::make_heapstd::sort_heap, bạn có thể đi sâu hơn một cấp độ và tự viết các hàm đó theo nghĩa std::push_heapstd::pop_heaptương ứng:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

Thư viện Chuẩn chỉ định cả hai push_heappop_heapnhư là độ phức tạp O(log N). Tuy nhiên, lưu ý rằng vòng lặp bên ngoài trên phạm vi [first, last)dẫn đến O(N log N)độ phức tạp make_heap, trong khi std::make_heapchỉ có O(N)độ phức tạp. Đối với sự O(N log N)phức tạp tổng thể của heap_sortnó không quan trọng.

Chi tiết bị bỏ qua : O(N)triển khaimake_heap

Thử nghiệm

Dưới đây là bốn Ví dụ trực tiếp ( C ++ 14 , C ++ 11 , C ++ 98 và Boost , C ++ 98 ) kiểm tra tất cả năm thuật toán trên nhiều đầu vào khác nhau (không có nghĩa là đầy đủ hoặc nghiêm ngặt). Chỉ cần lưu ý sự khác biệt rất lớn trong LOC: C ++ 11 / C ++ 14 cần khoảng 130 LOC, C ++ 98 và Boost 190 (+ 50%) và C ++ 98 hơn 270 (+ 100%).

14
Morwenn 2016-05-09 12:55.

Một cái khác nhỏ và khá thanh lịch ban đầu được tìm thấy trong bài đánh giá mã . Tôi nghĩ nó đáng được chia sẻ.

Đếm sắp xếp

Mặc dù nó khá chuyên biệt, sắp xếp đếm là một thuật toán sắp xếp số nguyên đơn giản và thường có thể thực sự nhanh với điều kiện các giá trị của các số nguyên cần sắp xếp không quá xa nhau. Nó có lẽ lý tưởng nếu một người cần sắp xếp một tập hợp một triệu số nguyên được biết là từ 0 đến 100 chẳng hạn.

Để thực hiện một kiểu đếm rất đơn giản hoạt động với cả số nguyên có dấu và không dấu, người ta cần tìm phần tử nhỏ nhất và lớn nhất trong tập hợp để sắp xếp; sự khác biệt của chúng sẽ cho biết kích thước của mảng số lượng cần phân bổ. Sau đó, bước thứ hai qua bộ sưu tập được thực hiện để đếm số lần xuất hiện của mọi phần tử. Cuối cùng, chúng tôi ghi lại số lượng yêu cầu của mọi số nguyên trở lại bộ sưu tập ban đầu.

template<typename ForwardIterator>
void counting_sort(ForwardIterator first, ForwardIterator last)
{
    if (first == last || std::next(first) == last) return;

    auto minmax = std::minmax_element(first, last);  // avoid if possible.
    auto min = *minmax.first;
    auto max = *minmax.second;
    if (min == max) return;

    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type;
    std::vector<difference_type> counts(max - min + 1, 0);

    for (auto it = first ; it != last ; ++it) {
        ++counts[*it - min];
    }

    for (auto count: counts) {
        first = std::fill_n(first, count, min++);
    }
}

Mặc dù nó chỉ hữu ích khi phạm vi của các số nguyên cần sắp xếp được biết là nhỏ (thường không lớn hơn kích thước của tập hợp để sắp xếp), việc đếm sắp xếp chung chung hơn sẽ khiến nó chậm hơn trong các trường hợp tốt nhất. Nếu phạm vi không được biết là nhỏ, có thể sử dụng một thuật toán khác như sắp xếp cơ số , ska_sort hoặc spreadort .

Chi tiết bị bỏ qua :

  • Chúng tôi có thể đã vượt qua giới hạn của phạm vi giá trị được thuật toán chấp nhận làm tham số để loại bỏ hoàn toàn lần đầu tiên std::minmax_elementqua bộ sưu tập. Điều này sẽ làm cho thuật toán thậm chí còn nhanh hơn khi giới hạn phạm vi nhỏ hữu ích được biết bằng các phương tiện khác. (Nó không phải là chính xác; đi qua một hằng số 0 đến 100 vẫn còn nhiều hơn một đường chuyền thêm hơn một triệu các yếu tố để phát hiện ra rằng các giới hạn thực sự là 1 đến 95. Thậm chí 0-1000 sẽ có giá trị nó; sự các phần tử phụ được viết một lần bằng 0 và đọc một lần).

  • Phát triển countsnhanh chóng là một cách khác để tránh vượt qua lần đầu tiên riêng biệt. Nhân đôi countskích thước mỗi khi nó phải tăng lên sẽ mang lại thời gian O (1) phân bổ cho mỗi phần tử được sắp xếp (xem phân tích chi phí chèn bảng băm để biết bằng chứng rằng tăng trưởng theo cấp số nhân là chìa khóa). Việc phát triển cuối cùng cho một cái mới maxthật dễ dàng với std::vector::resizeviệc thêm các phần tử 0 mới. minCó thể thực hiện việc thay đổi nhanh chóng và chèn các phần tử mới bằng 0 ở phía trước std::copy_backwardsau khi phát triển vector. Sau đó std::fillđể không các phần tử mới.

  • Các countsvòng lặp increment là một biểu đồ. Nếu dữ liệu có khả năng lặp lại cao và số lượng thùng ít, bạn có thể hủy cuộn qua nhiều mảng để giảm tắc nghẽn phụ thuộc dữ liệu tuần tự khi lưu trữ / tải lại vào cùng một thùng. Điều này có nghĩa là nhiều số đếm đến 0 ở đầu và nhiều hơn nữa để lặp lại ở cuối, nhưng sẽ đáng giá trên hầu hết các CPU, ví dụ như hàng triệu số 0 đến 100 của chúng tôi, đặc biệt nếu đầu vào có thể đã được sắp xếp (một phần) và có cùng một số chạy dài.

  • Trong thuật toán trên, chúng tôi sử dụng một min == maxséc để trả về sớm khi mọi phần tử có cùng giá trị (trong trường hợp đó tập hợp được sắp xếp). Thay vào đó, thực sự có thể kiểm tra đầy đủ xem bộ sưu tập đã được sắp xếp hay chưa trong khi tìm các giá trị cực đại của bộ sưu tập mà không bị lãng phí thời gian bổ sung (nếu lần vượt qua đầu tiên vẫn bị tắc nghẽn bộ nhớ với công việc cập nhật tối thiểu và tối đa). Tuy nhiên, một thuật toán như vậy không tồn tại trong thư viện tiêu chuẩn và việc viết một thuật toán sẽ tẻ nhạt hơn so với việc viết phần còn lại của bản sắp xếp đếm. Nó được để lại như một bài tập cho người đọc.

  • Vì thuật toán chỉ hoạt động với các giá trị số nguyên, các xác nhận tĩnh có thể được sử dụng để ngăn người dùng mắc lỗi kiểu rõ ràng. Trong một số bối cảnh, lỗi thay thế bằng std::enable_if_tcó thể được ưu tiên hơn.

  • Trong khi C ++ hiện đại đã tuyệt, thì C ++ trong tương lai có thể còn tuyệt hơn: các ràng buộc có cấu trúc và một số phần của Ranges TS sẽ làm cho thuật toán trở nên sạch hơn.

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Tận dụng lợi thế của việc bán hàng nhân Ngày của Cha này

Tận dụng lợi thế của việc bán hàng nhân Ngày của Cha này

Màn hình Samsung Galaxy S9 Plus. Chủ nhật này là Ngày của Cha⁠ — trong trường hợp nó khiến bạn suy nghĩ — và thay vì mua cho anh ấy một chiếc cà vạt trong năm nay, có lẽ đã đến lúc bạn mua cho anh ấy thứ mà anh ấy sẽ thực sự sử dụng.

Assassin's Creed Snuck Into Monster Hunter: World Last Night

Assassin's Creed Snuck Into Monster Hunter: World Last Night

Monster Hunter: World yêu thích các sự kiện chéo. Dù có nghĩa là hóa trang thành Dante của Devil May Cry, giả dạng Horizon: Zero Dawn's Aloy, hay chiến đấu với quái vật Final Fantasy, các nhiệm vụ sự kiện khác nhau của Thế giới được nâng cấp tự do so với các trò chơi khác.

Ava DuVernay Có Quà Tặng Ngày Của Mẹ cho Tất Cả Chúng Ta: Nếp Nhăn Thời Gian Sẽ Được Viết Lại Vào Cuối Tuần Ngày Của Mẹ!

Ava DuVernay Có Quà Tặng Ngày Của Mẹ cho Tất Cả Chúng Ta: Nếp Nhăn Thời Gian Sẽ Được Viết Lại Vào Cuối Tuần Ngày Của Mẹ!

Storm Reid, Oprah Winfrey, Mindy Kaling, Reese Witherspoon và Ava DuVernay tại buổi chiếu đặc biệt của A Wrinkle in Time tại Nhà hát Walter Reade ở Thành phố New York vào ngày 7 tháng 3 năm 2018 “Ava rất mong được nói chuyện với bạn,” một trong những người của Array dư luận viên nói qua điện thoại. (Array là tập thể phân phối, nghệ thuật và vận động chính sách của Ava DuVernay tập trung vào các bộ phim của người da màu và phụ nữ.

Nhiệm vụ bất khả thi 5 sẽ khôi phục niềm tin của bạn trong phim hành động Tentpole

Nhiệm vụ bất khả thi 5 sẽ khôi phục niềm tin của bạn trong phim hành động Tentpole

Mission Impossible: Rogue Nation bắt đầu ở một cấp độ khác. Theo nghĩa đen.

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

McCain, người đang làm việc cho một album mới, lần đầu tiên bước vào vòng kết nối vào tối thứ Sáu ở Nashville

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Tôi viết như thế nào

Tôi viết như thế nào

Đối với tôi, mọi thứ là về dòng đầu tiên đó và nó sẽ đưa bạn đến đâu. Một số nhà văn bị điều khiển bởi cốt truyện, sự sắp xếp tinh tế của các quân cờ, trong khi những người khác bị lôi cuốn bởi một nhân vật và khả năng thực hiện một cuộc hành trình với một người bạn hư cấu mới.

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Language