排序2-选择排序

1、基本思想
顾名思义，选择排序就是每次选一个数据放到其应该出现的位置，以升序（降序）为例，首先选最小（最大）的数据放到正确位置，接着再选次小（次大）的数据放到合适的位置，以此类推，直到最大（最小）的数据被放入最后一个位置，排序就算完成。

总体算法分三步完成：选数据--->将所选数据放入合适位置--->缩小需要排序的范围

图解（以升序为例）：

image

2、排序效果图：

image

3、时间复杂度&&空间复杂度

选择排序的比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数：

N=(n-1)+(n-2)+...+1=n*(n-1)/2。

交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。

故此，选择排序的时间复杂度为O(N^2)。

选择排序的空间复杂度为O(1)。

http://blog.csdn.net/snow_5288/article/details/59109966