选择排序算法

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

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?