疯狂荷花

文章
5
资源
0
加入时间
2年10月17天

寻找第k大or第k小的数-->寻找中位数

快排思想,选取数组中第一个元素e为参考元素,利用partition() 使得数组左边的元素全都不大于e,数组右边的元素全都不小于e–>升序排序设数组长度为n,若e的下标m恰好为n-k,则寻找到k大的元素,即e;若e的下标m恰好为k-1,则寻找到第小的元素,即e如果m>n-k,在e元素的左半边递归寻找;如果m<n-k, 在e元素的右半边递归寻找如果m>k-1,在e元素的左半边递归寻找;如果m<k-1, 在e元素的右半边递归寻找