选择类

简单选择排序

每趟选择出一个最值，与无序序列中的第一个交换

1. 【最坏时间复杂度】$O(n^2)$；两层循环的执行次数和初始序列没有关系，执行次数(n-1+1)(n-1)/2=n(n-1)/2
2. 【空间复杂度】$O(1)$
3. 【评价】没有利用上次选择时比较的结果，所以之后出现了树形选择排序和堆排序

简单选择排序稳定性分析

	情况一：交换版（默认版本）	情况二：插入版（如果有特殊交代）
说明	4(1)、3、4(2)、1、5 选择出最小值1，和4(1)交换1、3、4(2)、4(1)、5	选出的最值插入到有序序列中
稳定性	不稳定	稳定
适合情况	数组	链表

树形选择排序

又称锦标赛排序

思路

1. 有n个待排序的元素，把它们两两一组进行比较，取出较小的
2. 然后在这n/2个较小者中再两两一组进行比较，取出较小的
3. 重复上述步骤，直到取出最小元素
4. 这个过程用一棵满二叉树表示，在选出最小关元素后，将这个元素对应的叶子节点的值置为∞，然后把不为∞的兄弟节点移到父节点的位置

1. 【时间复杂度】$O(nlogn)$；完全二叉树的深度为[log2n]+1，所以每选出一个最小元素需要进行[log2n][log2n]次比较，移动元素的次数小于等于比较次数
2. 【评价】这种排序方法辅助存储空间较多、和“最大值”进行多余的比较等缺点。在此基础上改进诞生了堆排序

堆排序

用堆来选择最值

1. 【空间复杂度】就地建堆，空间复杂度为O(1)
2. 【时间复杂度】$O(nlo{g}_{2}n)$