1.选择排序
1.1简介
思路：遍历一遍，选出最大值和最小值的下标，然后与第一个和最后一个数字交换位置。
1.2代码
1.3分析
最好复杂度：O(N^2)
最差复杂度：O(N^2)
理论上，在数据量较大情况下，这是一个比冒泡排序效率 略好 的排序算法。
略好：一次换两个数，所以等差数列是n,n-2,n-4…冒泡等差数列是n,n-1,n-2…
2.堆排序
堆排序也是选择排序的一种，也是选一个最值放到最后面，再选一个次最值，放到倒数第二的位置，唯一的区别是借助了堆这个数据结构。
2.1简介
堆排：先建堆，后排序
- 建堆：向下调整算法建堆。
为什么不用向上调整算法建堆？
思考：向上调整算法与向下调整算法同为调整算法，且时间复杂度都为O(logN),为什么向下调整算法建堆的时间复杂度为O(N)，而向上调整算法却到达了O(N*logN)?
答：
说的简单一点，对于单个结点的向上调整/向下调整，都大概最差要调整高度次，也就是差不多是logN，但是对于一整个堆而言，这个堆中如果用向上调整算法，第一行不需要调整，如果用向下调整算法，最后一行不需要调整，而往往在N足够大的情况下，最后一行的结点个数占百分之50左右。
- 排序：首尾交换，然后向下调整算法使其成堆。
小堆 --> 降序
大堆 --> 升序
2.2代码
2.3分析
向下调整算法时间复杂度：O(logN)
向下调整算法时间复杂度：O(logN)
数组从后向前建堆：O(N)
原因：最后一排占数据的大多数，却没有进行向下调整(最后一排下面没有数字)
堆排序 = 建堆 + 排序 = O(N*logN)
堆排与希尔排序的适应性：
堆排序与希尔排序是一个效率量级的，两者区别在于在数据大量具有相同的数字时候，希尔会快一些，数据大部分都不一样的时候，堆排快一些。
EOF
