每一轮都先找出"剩下里面最小的那个"，再把它放到该在的位置上——交换次数比冒泡排序少得多。
选择排序的思路换了个角度：冒泡排序是"相邻的两个比一比，谁大谁往后"；选择排序则是每一轮先把剩下还没排好的部分整个看一遍，找出其中最小的那个，然后把它和这一轮"应该放的位置"交换。第一轮找出整个数组的最小值放到第 1 位，第二轮在剩下的部分里找最小值放到第 2 位，以此类推。
还是用 {5, 2, 8, 1, 9} 演示。外层循环控制"现在要确定第几个位置"，内层循环负责"在剩下的范围里找最小值的下标"：
| 1 | void SelectionSort(int arr[], int n) |
| 2 | { |
| 3 | for (int i = 0; i < n - 1; i++) // 确定第 i 个位置该放谁 |
| 4 | { |
| 5 | int minIndex = i; // 先假设当前位置就是最小值 |
| 6 | for (int j = i + 1; j < n; j++) // 在剩下的部分里找真正的最小值 |
| 7 | { |
| 8 | if (arr[j] < arr[minIndex]) |
| 9 | { |
| 10 | minIndex = j; |
| 11 | } |
| 12 | } |
| 13 | int temp = arr[i]; // 把找到的最小值换到第 i 位 |
| 14 | arr[i] = arr[minIndex]; |
| 15 | arr[minIndex] = temp; |
| 16 | } |
| 17 | } |
minIndex，但不真正移动任何数据），找完一整轮才做一次交换——这是选择排序和冒泡排序最大的写法差异：冒泡是"边比边换"，选择是"先找全，再换一次"。冒泡排序每发现一对顺序错误的相邻数，就立刻交换一次——一轮下来可能交换很多次。选择排序则不一样：每一轮，无论内层循环比较了多少次，最多只会真正交换一次（找到最小值之后，和当前位置换一下）。如果"交换"这个操作的代价比"比较"更高（比如交换的是很大的结构体，不只是几个整数），选择排序往往更划算。
n-1=19 次，部分轮次"最小值已经在对的位置"时甚至不需要真正移动）。不过两者的比较次数是一样多的（都是约 n²/2 次）——选择排序省的是交换，不是比较。| 排序方式 | 比较次数 | 交换次数 | 时间复杂度 |
|---|---|---|---|
| 冒泡排序 | 约 n²/2 | 最坏约 n²/2，最好 0 | O(n²)，最好情况可优化到 O(n) |
| 选择排序 | 约 n²/2 | 固定最多 n-1 次 | O(n²)，无法用"提前结束"优化 |