排序算法 - （简单）选择排序 (Selection Sort）

基本思路

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

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

性能

时间复杂度：O(n²)

空间复杂度：O(1)

示例代码

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

 1private static int[] selectionSort(int[] unsortedArray) {
 2    int minIndex;
 3    for (int round = 0; round < unsortedArray.length; round ++) {
 4        // Should have N rounds
 5
 6        minIndex = round;
 7
 8        for (int j = round + 1; j < unsortedArray.length; j ++) {
 9            if (unsortedArray[minIndex] > unsortedArray[j]) {
10                minIndex = j;
11            }
12        }
13
14        if (minIndex != round) {
15            int temp = unsortedArray[minIndex];
16            unsortedArray[minIndex] = unsortedArray[round];
17            unsortedArray[round] = temp;
18        }
19    }
20
21    return unsortedArray;
22}

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

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