选择排序是所以用到它的时候,数据规模越小越好。
时间复杂度:无最好最坏,永远都是O(n2)
不占用额外空间(唯一好处)
还不稳定(几乎已经被淘汰了的排序算法)
共n-1圈,
第一圈找到最小(最大)的值的位置,选择与第一个位置的值交换位置
第一圈找到第二小(第二大)的值的位置,选择与第二个位置的值交换位置
第一圈找到第三小(第三大)的值的位置,选择与第三个位置的值交换位置
…………
第 n-1 圈找到第n-1 小(n-1大)的值的位置,选择与第n-1个位置的值交换位置
完
void selection_sort( vector<T>& arr) { //升序
for (int i = 0; i < arr.size() - 1; i++) {
int min = i; //假设第一个值是最小值
for (int j = i + 1; j < arr.size(); j++) //与其他n-1个值比较,如果有更小的就交换位置,一圈下来,第一个位置的值就是真正的最小了
if (arr[j] < arr[min])
min = j;
swap(arr[i], arr[min]);
}
}