DraculaW

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  19 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks

// 給一個數組a[n]求其中 第k大的數值的算法
// 基本的思想就是 使用quicksort的一個變種
// 每次進行完part后 判斷它的返回值 是否為k
// 如果為k 返回
// 如果大于k 則在返回的位置的前面找
// 如果小于k 則在返回的位置的后面找

int part(int* a, int start, int end)
{
    int t = a[end-1];
    int e = -2;
    while(start < e)
    {
        while(a[start]<t) start++;
        while(a[e]>t) e--;
        int tmp = a[e];
        a[e] = a[start];
        a[start] = tmp;
    }
    return start;
}



int findK(int* a, int start, int end, int k)
{
    int i = part(a, start, end);
    int rtn;

    if(i < k-1)
    {
        rtn = findK(a, i+1, end);
    }

    else if(i > k-1)
    {
        rtn = findK(a, start, i-1);
    }
    else
    {
        rtn = a[i];
    }

    return rtn;
}
posted on 2007-11-15 20:31 DraculaW 阅读(836) 评论(1)  编辑 收藏 引用

评论

# re: 給出一個數組a[n] 求 第k大的值[未登录] 2009-08-21 16:50 hzx
递归里面的findK(a, i+1, end);少参数  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理