选择排序通过对每次通过失败仅进行一次交换来增强气泡排序。为了做到这一点, 选择排序会在通过时搜索最大的值, 并在完成通过后将其放置在最佳区域。与气泡排序类似, 在第一遍之后, 最大的项目在正确的位置。在第二遍之后, 将设置以下最大值。此过程将继续进行, 并且需要n-1来对n个项目进行排序, 因为必须在第（n-1）次传递之后设置最后一个项目。
ALGORITHM: SELECTION SORT (A)1. k ← length [A]2. for j ←1 to n-13. smallest ←j4. for I ← j + 1 to k5. if A [i] <
A [ smallest]6. then smallest ←i7. exchange (A [j], A [smallest])分析
- 输入：给出n个元素。
- 输出：进行排序所需的比较数。
- 逻辑：如果我们在选择排序中有n个元素, 则需要n-1次通过才能找到排序后的数组。
In pass 1: n-1 comparisons are required In pass 2:n-2 comparisons are required In pass 3: n-3 comparisons are required........................................................................................................................................................... In pass n-1: 1 comparison is required Total comparisons: T (n) = (n-1) + (n-2) + (n-3) +........+ 1= = o (n2) Therefore complexity is of order n2例：
使用选择排序对以下数组进行排序：A [] =（7, 4, 3, 6, 5）。
A [] =
| 7 | 4 | 3 | 6 | 5 |
Smallest =74 <
7, smallest = 43 <
4, smallest = 36 >
3, smallest = 35 >
3, smallest = 3交换7和3
| 3 | 4 | 7 | 6 | 5 |
Smallest = 44 <
7, smallest = 44 <
6, smallest = 44 <
5, smallest = 4无掉期
| 3 | 4 | 7 | 6 | 5 |
Smallest = 76 <
7, smallest = 65 <
7, smallest = 5【选择排序算法】交换7和5
| 3 | 4 | 5 | 6 | 7 |
Smallest = 66<
7, smallest = 6无掉期
| 3 | 4 | 5 | 6 | 7 |
| 3 | 4 | 5 | 6 | 7 |
