sort — сортировка в C++

Структуры и функции   25 Март 2012  Автор статьи:  

Функция sort сортирует контейнер на полуинтервале [first, last) с помощью библиотечной сортировки IntroSort. Данная сортировка гарантирует наилучшее время сортировки.
Библиотека
algorithm
Способы вызова функции
template
void sort ( RandomAccessIterator first, RandomAccessIterator last );

template
void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

Где

  • first — итератор на первый элемент
  • last — итератор на последний элемент
  • comp — компаратор, согласно которому будет произведена сортировка элементов в контейнере

Сложность

O(n\times\log{n}), где n — длина сортируемого отрезка.

Примеры

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
#define NMAX 4000000
using namespace std;
int arr[NMAX];
vector <int> vec(NMAX);
int comp(int a, int b)
{
  return a - b;
}
int main()
{
    sort(arr, arr + NMAX);
    //сортирую весь массив
    sort(vec.begin(), vec.end());
    //сортирую весь вектор
    sort(arr, arr + NMAX, comp);
    //сортирую массив по компаратору
    return 0;
}

Замечания
Хороший выбор для практически всех случаев. Является отличной реализацией IntroSort. Лучше работают только сортировки основанные на специфики ключа, такие как цифровая сортировка или сортировка подсчетом. Использование компаратора дает возможность сортировать элементы для которых по умолчанию не определены операции сравнения или сортировать элементы в порядке отличном от стандартного. Таким образом с помощью компараторов вы сможете сортировать свои структуры или сортировать числа по четности например.

Научиться программировать

  • на Delphi

  • на Java

  • на C++