std::sort алгоритм (и его двоюродные братьяstd::partial_sort а такжеstd::nth_element) из стандартной библиотеки C ++ в большинстве реализацийсложное и гибридное объединение более элементарных алгоритмов сортировки, например, сортировка выбора, вставка, быстрая сортировка, сортировка слиянием или сортировка в куче.

Есть много вопросов здесь и на родственных сайтах, таких какhttps://codereview.stackexchange.com/ связанные с ошибками, сложностью и другими аспектами реализации этих классических алгоритмов сортировки. Большинство предлагаемых реализаций состоят из необработанных циклов, используют манипуляции с индексами и конкретные типы, и, как правило, нетривиальны для анализа с точки зрения правильности и эффективности.

Вопрос: как можно реализовать вышеупомянутые классические алгоритмы сортировки с использованием современного C ++?

нет сырых петель, но объединяя алгоритмические строительные блоки Стандартной библиотеки из<algorithm>интерфейс итератора и использованиешаблоны вместо манипулирования индексами и конкретными типамиСтиль C ++ 14, включая полную стандартную библиотеку, а также синтаксические шумоподавители, такие какauto, шаблонные псевдонимы, прозрачные компараторы и полиморфные лямбды.

Заметки:

дальнейшие ссылки на реализации алгоритмов сортировки см.Википедия, Розетта код или жеhttp://www.sorting-algorithms.com/в соответствии сСоглашения Шона Родителя (слайд 39), необработанный цикл представляет собойforпетли длиннее, чем композиция двух функций с оператором. Такf(g(x)); или жеf(x); g(x); или жеf(x) + g(x); не являются необработанными циклами, и не являются циклами вselection_sort а такжеinsertion_sort ниже.Я следую терминологии Скотта Мейерса, чтобы обозначить текущий C ++ 1y уже как C ++ 14, и обозначить C ++ 98 и C ++ 03 как C ++ 98, так что не расстраивайтесь.Как предложено в комментариях @Mehrdad, в конце ответа я приведу четыре реализации в качестве живого примера: C ++ 14, C ++ 11, C ++ 98 и Boost и C ++ 98.Сам ответ представлен только на языке C ++ 14. Где уместно, я обозначаю синтаксические и библиотечные различия, где разные языковые версии различаются.