В данной статье будет затронута весьма популярная тема в области программирования, а именно Сортировка массива в C++. Здесь приведено несколько способов сортировки вместе с примерами.

Сортировка выбором
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

template<typename T>
void select_sort(T a[], int size)
{
    int k;
    T x;

    for(int i = 0; i < size; ++i)        // i - номер текущего шага
    {
        k = i; 
        x = a[i];
        for(int j = i + 1; j < size; ++j)// цикл выбора наименьшего элемента
            if ( a[j] < x ) 
            {
                k = j;                    // k - индекс наименьшего элемента
                x = a[j]; 
            }
        a[k] = a[i]; 
        a[i] = x;                        // меняем местами наименьший с a[i]
    }
}

Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.

Сортировка пузырьком

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

template<typename T>
void bubble_sort(T a[], int size) {
    T x;

    for(int i = 0; i < size; ++i) // i - номер прохода
    {            
        for(int j = size - 1; j > i; --j) // внутренний цикл прохода
        {     
            if ( a[j-1] > a[j] ) 
            {
                x = a[j-1]; 
                a[j-1] = a[j];
                a[j] = x;
            }
        }
    }
}

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому — почти не применяется.

Сортировка вставками

Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

template<typename T>
void insert_sort(T a[], int size) 
{
    T x;
    int j;

    for (int i = 0; i < size; ++i) 
    {  
        x = a[i];   
        // поиск места элемента в готовой последовательности 
        for (j = i - 1; j >= 0 && a[j] > x; --j)
            a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
        a[j+1] = x;
    }
}

Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как Theta(n2), дополнительная память при этом не используется.

Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.

Ну Собственно проверка

template<typename T>
void out_arr(T arr[], int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << arr[i] << " ";
}

int main()
{
    int arr0[6] = {9,5,4,6,2,1};
    int arr1[6] = {9,5,4,6,2,1};
    int arr2[6] = {9,5,4,6,2,1};
    select_sort(arr0, 6);
    bubble_sort(arr1, 6);
    insert_sort(arr2, 6);

    out_arr(arr0, 6); std::cout << '\n'; 
    out_arr(arr1, 6); std::cout << '\n'; 
    out_arr(arr2, 6); std::cout << '\n'; 

    return 0;
}

Имхо лучше юзать std::sort().

#include <iostream>
#include <algorithm>
#include <functional>

int main()
{
    int arr[] = {9,8,7,6,5,4,3,2,1};
    int size = sizeof(arr)/sizeof(int);

    std::sort(arr, arr + size);
    std::copy(arr, arr + size, std::ostream_iterator<int>(std::cout," "));
    std::cout << '\n';

    std::sort(arr, arr + size,std::greater<int>());
    std::copy(arr, arr + size, std::ostream_iterator<int>(std::cout," "));
    std::cout << '\n';
    return 0;
}

PS.
Если вы новичок,и не понимаете,что такое template или не проходили этого, то есть два способа справиться с этой проблемой:
1. Загуглить «Шаблоны С++. Материал простой,разберетесь»
2. Убрать эту надпись,а в прототипе букву T заменить типом вашего массива (int, double,..etc)