排序算法之取舍排序(Selection Sort)

排序算法之选择排序(Selection Sort)
选择排序

1.伪代码
对于初始n个元素的数列a[1...n]
选择排序实现的伪代码如下：

for i = 1 : n      k = i      for  j = i + 1 : n,              if a[j] < a[k]                  k = j       ->a[k]是a[i...n]中最小的元素       交换a[i], a[k]      -> 排好序的元素：a[1...i]end 

2. 算法过程
初始无序数列：5, 2, 3, 1, 4
i = 1
[
    k = 1
    j = 2
   因为 a[j] < a[k]
   所以 k = j

   k = 2
   j = 3
   因为 a[j] > a[k]
   所以 k不变

   k = 2
   j = 4
   因为 a[j] < a[k]
   所以 k = j

   k = 4
   j = 5
   因为 a[j] > a[k]
   所以k不变
]
a[i]与 a[k]交换
最后结果为：1, 2, 3, 5, 4

i =  2
[
   过程和上面类似
]

3.算法特性
非稳定的。
空间复杂度：O(1)
时间复杂度：比较的次数,O(n^2)；交换的次数O(n)

4.总结
选择排序算法的优点是交换的次数是最小的，因此对于交换的操作复杂度非常高的情况下，可以选择使用选择排序算法。