选择排序算法

选择排序通过对每次通过失败仅进行一次交换来增强气泡排序。为了做到这一点, 选择排序会在通过时搜索最大的值, 并在完成通过后将其放置在最佳区域。与气泡排序类似, 在第一遍之后, 最大的项目在正确的位置。在第二遍之后, 将设置以下最大值。此过程将继续进行, 并且需要n-1来对n个项目进行排序, 因为必须在第（n-1）次传递之后设置最后一个项目。

ALGORITHM: SELECTION SORT (A)
1. k ← length [A]
2. for j ←1 to n-1
3. smallest ←  j
4. for I ← j + 1 to k
5. if A [i] < A [ smallest]
6. then smallest ←  i
7. exchange (A [j], A [smallest])

分析

1. 输入：给出n个元素。
2. 输出：进行排序所需的比较数。
3. 逻辑：如果我们在选择排序中有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

1个迭代：

Smallest =7
      4 < 7, smallest = 4
      3 < 4, smallest = 3
   6 > 3, smallest = 3
   5 > 3, smallest = 3

交换7和3

3

4

7

6

5

第二次迭代：

Smallest = 4
4 < 7, smallest = 4
4 < 6, smallest = 4
4 < 5, smallest = 4

无掉期

3

4

7

6

5

第三次迭代：

Smallest = 7
6 < 7, smallest = 6
5 < 7, smallest = 5

交换7和5

3

4

5

6

7

第4次迭代：

Smallest = 6
6< 7, smallest = 6

无掉期

3

4

5

6

7

最后, 排序后的列表是：

3

4

5

6

7

---