Найдите минимум и поместите его в левый конец
Сложность
- O(n²)
Алгоритм
- Выберите первый элемент списка
- найти наименьший элемент среди остальных
- поменять местами первый элемент с наименьшим
- повторяйте 1 ~ 3 со вторым элементом, пока не дойдете до конца списка
Сравнение с пузырьковой сортировкой
Сортировка выбором чем-то похожа на пузырьковую сортировку. Всего два отличия.
- Найдите наименьший и поместите его в левый конец. (сортировка пузырьком в конечном итоге приводит к правильному концу)
- не нужно постоянно менять местами все элементы, а просто поменять местами самые маленькие. (пузырьковая сортировка продолжает менять местами все элементы, перенося самый большой в правый конец)
питон
def selectionsort(list): for i in range(len(list) - 1): minIndex = i for j in range(i+1, len(list)): if list[j] < list[minIndex]: minIndex = j list[i], list[minIndex] = list[minIndex], list[i] return list list = [12,4,7,4,67,8,9,3,2,7,98,6,4] print(selectionsort(list))
C++
#include <iostream> using namespace std; int minIndex; void selection(int a[], int s){ for(int i = 0; i < s-1; i++){ minIndex = i; for(int j = i+1; j < s; j++){ if(a[j] < a[minIndex]){ minIndex = j; } } swap(a[i], a[minIndex]); } } int main() { int a[5] = {5,4,3,1,2}; selection(a, 5); for(int i = 0; i < n; i++){ cout<<a[i]<<endl; } }