基本思路

假设按照从小到大排列，总共有n个元素

• 第一轮，找出数组中最小的元素，与第一个元素交换
• 第二轮，找出剩余元素中最小的元素，与第二个元素交换
• 第三轮，找出剩余元素中最小的元素，与第三个元素交换
• 如此重复上述步骤，直至处理完所有元素

性能

时间复杂度：O(n²)

空间复杂度：O(1)

示例代码

更多详情可点击链接参考示例代码

private static int[] selectionSort(int[] unsortedArray) {
    int minIndex;
    for (int round = 0; round < unsortedArray.length; round ++) {
        // Should have N rounds

        minIndex = round;

        for (int j = round + 1; j < unsortedArray.length; j ++) {
            if (unsortedArray[minIndex] > unsortedArray[j]) {
                minIndex = j;
            }
        }

        if (minIndex != round) {
            int temp = unsortedArray[minIndex];
            unsortedArray[minIndex] = unsortedArray[round];
            unsortedArray[round] = temp;
        }
    }

    return unsortedArray;
}

跑一下测试数据，可以看到类似于下面的结果

Before sort: 3, 2, 9, 6, 0, 4, 8, 5, 7, 1
After round 1: 0, 2, 9, 6, 3, 4, 8, 5, 7, 1
After round 2: 0, 1, 9, 6, 3, 4, 8, 5, 7, 2
After round 3: 0, 1, 2, 6, 3, 4, 8, 5, 7, 9
After round 4: 0, 1, 2, 3, 6, 4, 8, 5, 7, 9
After round 5: 0, 1, 2, 3, 4, 6, 8, 5, 7, 9
After round 6: 0, 1, 2, 3, 4, 5, 8, 6, 7, 9
After round 7: 0, 1, 2, 3, 4, 5, 6, 8, 7, 9
After round 8: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After round 9: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After round 10: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
After sort: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9