| 课程名称 |
| 学生姓名 |
| 实验名称 |
| 实验地点 |
|
| 1. |
| 给定N个数，求其中第K小的数 |
| 2. |
| 如果使用快速排序或者其他高效的排序算法，可以在O(nlogn)的时间下轻松得出第k小 |
| 考虑如何改进快速排序来减小复杂度，我们发现快排中，划分实际上是从数组a[l - r]中选取一个主元，使l到x的所有元素小于等于x，x到r的所有元素大于等于x，这样就能确定x的最终位置 |
| 也就是说每划分一次就能确定这个主元的最终位置，于是试图去构造第k个位置 |
| 所以只需要某次划分的q为第k个小标的时候，其实就已经找到了答案，而其左右是否有序不用考虑 |
| 于是划分时如果q = k就返回a[q]，如果q比目标下标小，就递归右区间，否则递归左区间即可 |
| 3. |
| QUCIK_SELECT(L,R,K) |
|
|
|
|
|
|
| 4. |
| 类似快速排序的分析方法，可以知道上述算法最坏情况是O(n^2)的。而该算法的平均性能比较好，又因为是随机化的，因此不存在哪种输入会导致最坏情况发生，通过分析该函数的期望运行时间E[T(n)]=O(n)，得出，在期望的线性时间内，我们可以找到任一顺序统计量，特别是中位数。 |
| 5. |
| Algorithm-Class-codes/project6 at main · MQFLLY/Algorithm-Class-codes (github.com) |