随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

寻找第i小元素

今天学习了求第i小元素,被书上忽悠了一下,他硬说是0(n)的复杂度,我怎么看怎么看就是快速排序的思路,只是省去一半的递归而已。我开始还以为真的就0(n)呢,自己还想了好久用一个循环搞定之,结果后来发现,o(n)是最理想情况了。哎。书上说的有个中位数来得到o(n)的求第i小元素的方法,可以我愚笨,没有看懂。我就不信他插入排序不算时间,然后递归一下求中卫数,能正确?反正我是没有看懂,也不敢实现了。只实现了快速排序思路的方法,而且还发现,我写了N遍快速排序了,居然还出错!我也发现我以前的写法也有错。哎,郁闷啊。继续加油吧。。坚持。。
奉上源代码:(没有什么,就是快排)
#include <stdio.h>
#include 
<stdlib.h>
#include 
<time.h>

//随机分隔,(就是快排的分割函数)
int RandomPartition(int nData[], int nBegin, int nEnd)
{
    
int i = nBegin + rand() % (nEnd - nBegin);

    
int nX = nData[i];
    nData[i] 
= nData[nBegin];
    nData[nBegin] 
= nX;
    
--nEnd;
    
while(nBegin < nEnd)
    {
        
while(nData[nEnd] > nX)
        {
            
--nEnd;
        }
        
if (nBegin < nEnd)
        {
            nData[nBegin] 
= nData[nEnd];
            nData[nEnd] 
= nX;
            
++nBegin;
        }

        
while (nData[nBegin] < nX)
        {
            
++nBegin;
        }
        
if (nBegin < nEnd)
        {
            nData[nEnd] 
= nData[nBegin];
            
--nEnd;
        }
    }

    nData[nBegin] 
= nX;
    
return nBegin;
}

//递归调用得到第i小元素
int RandomIzedRecursion(int nData[], int nBegin, int nEnd, int nPos)
{
    
if (nBegin >= nEnd - 1)        //如果nBegin,直接认为找到了该值
    {
        
return nData[nBegin];
    }
    
int i = RandomPartition(nData, nBegin, nEnd);    //分割两部分
    if (i == nPos)    //如果刚好分割符号就是nPos,就找到了这个值。
    {
        
return nData[i];
    }

    
if (i > nPos)        //i > nPos。这继续递归nBegin - i的区域。
    {
        
return RandomIzedRecursion(nData, nBegin, i, nPos);
    }
                        
//否则递归 i + 1, nEnd区域,不过这时候nPos要相应的改变为nPos - i - 1
    return RandomIzedRecursion(nData, i + 1, nEnd, nPos - i - 1);
    

}

//得到第i小元素
int RandomIzedSelect(int nData[], int nLen, int nPos)
{
    srand((size_t)time(NULL));
    
return RandomIzedRecursion(nData, 0, nLen, nPos);
}

int main()
{
    
int nData[10= {8,2,5,9,3,6,4,7,1,6};    //测试
    int nTest;
    
for (int i = 0; i < 10++i)
    {
        nTest 
= RandomIzedSelect(nData, 10, i);
        printf(
"%d ", nTest);
    }
    printf(
"\n");

    
for (int i = 0; i < 10++i)        //注意,这里是改变了原来的数据
    {
        printf(
"%d ", nData[i]);
    }
    printf(
"\n");
    system(
"pause");
    
return 0;
}


posted on 2009-04-27 19:36 shongbee2 阅读(790) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


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