选择排序
概述
- 内部排序
- 不稳定
- 最好最坏都是O(N2)
- 原地排序空间O(1)
思路
- 先从待排序列中找出最小（大）的元素，放到已排序列的首位
- 从待排序列中找出最小（大）的元素，追加到已排序列
- 重复2直到排序完成
实现
template
void selection_sort(vector& arr) {
for (int i = 0; i < arr.size() - 1; i++) {
// 因为这里要i和j（i后面地每一个元素）比较，所以i 很明显，这是一个基于比较（但是基于选择而不是交换）的排序，将每个元素与它后面地序列元素一一比较，找到最小的元素并交换位置
冒泡排序是，将每一个元素与后一个元素相比较，如果大于则交换位置
两个排序都需要跑n轮（n是待排元素个数），只是选择排序减少了交换的次数