十大排序的个人总结之——选择排序

一、选择排序：

选择排序是所以用到它的时候，数据规模越小越好。

时间复杂度：无最好最坏，永远都是O(n2)

不占用额外空间（唯一好处）

还不稳定（几乎已经被淘汰了的排序算法）

1. 算法步骤

共n-1圈，

第一圈找到最小（最大）的值的位置，选择与第一个位置的值交换位置

第一圈找到第二小（第二大）的值的位置，选择与第二个位置的值交换位置

第一圈找到第三小（第三大）的值的位置，选择与第三个位置的值交换位置

…………

第 n-1 圈找到第n-1 小（n-1大）的值的位置，选择与第n-1个位置的值交换位置

完

2. 动图演示

3.代码

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]);
        }
}