Сортировка выбором — это алгоритм сортировки на месте. Во входном массиве есть отсортированная часть и несортированная часть. Алгоритм неоднократно находит наименьший элемент в несортированной части массива и помещает его в конец отсортированной части массива.
Сначала алгоритм находит наименьший элемент в массиве, равный 1, и добавляет его к отсортированному массиву, затем алгоритм находит наименьший элемент в оставшемся массиве и так далее.
Выполнение
Вот реализация функции selection_sort
.
void selection_sort(int array[], int size)
{
int start_index = 0;
while(start_index < size)
{
int min_index = start_index;
for(int i = start_index+1; i < size; i++)
{
if(array[i] < array[min_index])
{
min_index = i;
}
}
std::swap(array[start_index], array[min_index]);
start_index++;
}
}
Вышеупомянутая функция работает только для целочисленного значения. Вот общая функция, которая работает для всех типов данных.
template<typename T>
void selection_sort(std::vector<T>& array)
{
typedef typename std::vector<T>::iterator Itr;
Itr itr = array.begin();
while(itr != array.end())
{
Itr itr_min = itr;
for(Itr i = itr + 1; i != array.end(); i++)
{
if(*i < *itr_min)
{
itr_min = i;
}
}
std::iter_swap(itr, itr_min);
itr++;
}
}
Функция может принимать вектор целых чисел, вектор символов или вектор строк, она сортирует их все. itr
— это итератор, изначально указывающий на первый элемент массива. itr_min
— это итератор, указывающий на наименьший элемент в диапазоне [i, array.end())
. Метод std::iter_swap
используется для замены итераторов itr
и itr_min
и помещает наименьший элемент диапазона в конец отсортированной части массива.
std::swap
поменять местами значения, тогда как std::iter_swap
поменять местами итераторы.
Вот результат после запуска универсальной функции.
C++ реализация сортировки выбором
#include <iostream>
#include <vector>
template<typename T>
void selection_sort(std::vector<T>& array)
{
typedef typename std::vector<T>::iterator Itr;
Itr itr = array.begin();
while(itr != array.end())
{
Itr itr_min = itr;
for(Itr i = itr + 1; i != array.end(); i++)
{
if(*i < *itr_min)
{
itr_min = i;
}
}
std::iter_swap(itr, itr_min);
itr++;
}
}
template<typename T>
void print(const std::vector<T>& array)
{
for(auto itr = array.begin(); itr != array.end(); itr++)
{
std::cout << *itr << " ";
}
std::cout << '\n';
}
int main()
{
std::vector<int> v({5, 3, 12, 2, 8});
std::cout << "Original Array :";
print(v);
selection_sort(v);
std::cout <<"Sorted Array :";
print(v);
std::cout << '\n';
std::vector<char> c({'t', 'q', 'a', 'r', 'p'});
std::cout << "Original Array :";
print(c);
selection_sort(c);
std::cout <<"Sorted Array :";
print(c);
std::cout << '\n';
std::vector<std::string> str({"code", "live", "love", "sing", "create"});
std::cout << "Original Array :";
print(str);
selection_sort(str);
std::cout <<"Sorted Array :";
print(str);
std::cout << '\n';
}
Вы можете просмотреть этот код на Github
Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы
Справочник конкурентоспособного программиста — Антти Лааксонен
Вам также может понравиться
Сортировка слиянием
Сортировка вставками
Быстрая сортировка
Сортировка пирамидой
Первоначально опубликовано на https://programmercave0.github.io 29 августа 2017 г.