Question

（一）直接选择排序法

Answer 1

选择排序法第一次扫描会找出最大或者最小值，放到正确的位置；第二次扫描会在剩余数据找出最大或者最小值，放到正确位置；以此类推，直到扫描完成。

因此我们可以发现，简单选择排序也是通过两层循环实现。
第一层循环：依次遍历序列当中的每一个元素
第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。

现有无序数组[6 2 4 1 5 9]

第一趟找到最小数1,放到最前边(与首位数字交换)
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |

第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换

第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置
交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
交换后:| 1 | 2 | 4 | 5 | 6 | 9 |

第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换

排序完毕输出正确结果[1 2 4 5 6 9]

第一趟找到最小数1的细节：
当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |

先把6取出来,让它扮演最小数
当前最小数6与其它数一一进行比较,发现更小数就交换角色
当前最小数6与2比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较
当前最小数2与4比较,不动
当前最小数2与1比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较
当前最小数1与5比较,不动
当前最小数1与9比较,不动,到达末尾
当前最小数1与当前首位数字进行位置交换,如下所示
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
完成一趟排序,其余步骤类似

稳定性：不稳定。由于选择排序是以最大或最小值直接与最前方未排序的键值交换，数据排序顺序很有可能被改变。

时间性能：无论是最坏情况、最佳情况还是平均情况都需要找到最大值（或最小值），因此其比较次数为n(n-1)/2次；时间复杂度为O(n²)。

适用范围：适用于数据量小或者有部分数据已经排序过的情况。