vlambda博客
学习文章列表

选择排序的思想

1. 在未排列的序列中找到最小的元素, 存放序列的起始位置
2. 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾, 循环直至所有元素都已经有序

实现

根据选择排序的思想,代码实现的时候需要有两层嵌套循环

• 内层循环就是逐一对未排序元素进行比较, 并选出次轮循环中最小的元素
• 外层循环N次之后所有的元素都变得有序了

Java实现

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        //找到这一轮最小的元素
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                //记录下最小元素的下标
                minIndex = j;
            }
        }
        //将最小值与i交换
        swap(arr, i, minIndex);
    }
}

复杂度

• 时间复杂度: O(n²)
• 空间复杂度: O(1)