选择排序(Selection sort) 是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，然后放到已排序的序列的末尾。以此类推，直到没有待排序的数据元素。

算法特性

• 稳定性

选择排序是不稳定的排序算法。

• 时间复杂度

选择排序的时间复杂度均为 O(n^2)，在所有情况下都是相同的，无论是最好、最坏还是平均情况。

• 空间复杂度

选择排序是原地排序算法，不需要额外的的存储空间，其空间复杂度为O(1)。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

动画演示

代码实现

Java代码:

public static int[] selectionSort(int[] sourceArray) {
    if (sourceArray == null || sourceArray.length < 2) {
        return sourceArray;
    }

    int[] array = Arrays.copyOf(sourceArray, sourceArray.length);

    // 总共要经过n-1轮
    for (int i = 0; i < array.length - 1; i++) {
        int min = i;

        for (int j = i + 1; j < array.length; j++) {
            if (array[min] > array[j]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }

        // 将找到的最小值和i位置所在值进行交换
        if (min != i) {
            swap(array, i, min);
        }
    }

    return array;
}

private static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

结语

感谢您的阅读，请动动您可爱的小手?

~点赞，留言，关注，分享 4暴击(∩_∩)