《算法二》选择排序算法及它的时间复杂度_选择排序的时间复杂度是多少

1.选择排序算法

选择排序算法的时间复杂度为O(N^2)
选择排序算法规则：
1.指定位置的数和后面的数比较
2.如果指定位置的数大，则两个数交换位置
3.向后移动一个位置，和指定位置的数进行比较
假设数组大小 n ,第一轮比较n-1次，最小的数排在了最前面
第二轮比较，第一个数已经是最小不用比较，此轮比较n-2次，第二小的排在第二个位置。
依次类推，最后一轮，一次比较，最后得出有序的数列

1.1 和冒泡排序算法相比

选择排序更优，两种算法时间复杂度相同，但是选择排序算法两数交换的次数明显要少，通常情况下选择排序更快。
1

Java代码示例

	/**
     * 选择排序
     * 时间复杂度O(N^2)
     *
     * @param list
     */
    public static void selectSort(List<Integer> list) {
        int size = list.size();
        for (int out = 0; out < size - 1; out++) {
            for (int in = out + 1; in < size; in++) {
                if (list.get(in) < list.get(out)) {
                    int tmp = list.get(in);
                    list.set(in, list.get(out));
                    list.set(out, tmp);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码下载地址：https://gitee.com/timezxp/algorithmic
参考书籍：https://www.javabbs.club/bbs/bbs/topic/86-1.html
至此，感谢！
欢迎添加关注！