总结

T1 快速排序

​排序原理​：选择一个基准值，将小于基准值的放在左边，大于基准值的放在右边，再递归对左右两个部分进行快速排序，直到排序完成。 ​实现原理​：

1. 计算基准值 x。
2. 通过基准值把原数组划分为左右两部分数组，使得左数组都小于 x 而右数组都大于 x。
3. 递归地对左右数组进行 两步直到划分的子数组有序。
4. 当子数组元素只有一个的时候，就认为它是有序的了。

T2 第K个数

这题只能用单臂快排的方法做。

就是先快速排序，然后找K在那边，直到只剩K这个数。至于怎么只排一边，请重读上一句话。

T3 归并排序

​排序原理​：

1. 分解——将待排序数组递归地分成两个子数组，直到每个子数组只有一个元素为止。
2. 合并——将排好序的子数组按照顺序合并成一个新的有序数组。
3. 递归调用——重复上述过程，直到所有子数组都被合并成一个有序数组

T4 求逆序对

这题只能用归并排序的方法做。

从题目里可以得知两个条件。

1：i<j

2：a[i]>a[j]；

那么我们可以在归并排序的第二步分解出来的左右数组，左数组的所有元素下标均小于右数组元素下标。当把右数组元素 往辅助数组放时，假设左数组还存在若干元素，对于左数组的任意元素a[j]，均满足上面逆序对的两个条件。所以能与a[j]构成逆序对的元素数量即为当前左数组剩余元素个数。

T5 数的位置

用二分排序来找数的起点和终点。

如果没有则输出'-1 -1'

T7 伐木工

今天我认为除附加题外最难的题

这题用二分答案来做

判断y米高的锯子能不能砍够M米的木头。 如果可以上调一下，如果不可以下调一下。 至于怎么找到答案，请重读上一句话。