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

发布时间:2024年01月01日

一、选择排序:

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

时间复杂度:无最好最坏,永远都是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]);
        }
}

文章来源:https://blog.csdn.net/QENGFENG/article/details/135317501
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。