2.5.6

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

非递归官网实现见:https://algs4.cs.princeton.edu/23quicksort/QuickPedantic.java.html

原本是和快速排序一块介绍的,将数组重新排列,使得 a[k] 正好是第 k 小的元素,k0 开始。
具体思路类似于二分查找,
先切分,如果切分位置小于 k,那么在右半部分继续切分,否则在左半部分继续切分。
直到切分位置正好等于 k,直接返回 a[k]

代码

/// <summary>
/// 使 a[k] 变为第 k 小的数,k 从 0 开始。
/// a[0] ~ a[k-1] 都小于等于 a[k], a[k+1]~a[n-1] 都大于等于 a[k]
/// </summary>
/// <typeparam name="T">元素类型。</typeparam>
/// <param name="a">需要调整的数组。</param>
/// <param name="k">序号。</param>
/// <param name="lo">起始下标。</param>
/// <param name="hi">终止下标。</param>
/// <returns></returns>
static T Select<T>(T[] a, int k, int lo, int hi) where T : IComparable<T>
{
    if (k > a.Length || k < 0)
        throw new ArgumentOutOfRangeException("select out of bound");
    if (lo >= hi)
        return a[lo];

    int i = Partition(a, lo, hi);
    if (i > k)
        return Select(a, k, lo, i - 1);
    else if (i < k)
        return Select(a, k, i + 1, hi);
    else
        return a[i];
}

另请参阅

SortApplication 库

上一题 下一题