Chinaunix首页 | 论坛 | 博客
  • 博客访问: 968496
  • 博文数量: 214
  • 博客积分: 10173
  • 博客等级: 上将
  • 技术积分: 1867
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-18 13:48
文章分类

全部博文(214)

文章存档

2012年(1)

2010年(13)

2009年(5)

2008年(98)

2007年(97)

分类: LINUX

2007-11-14 18:57:28

int partition(const int * na, int low, int hight);
int new_qsort(const int * na, int low, int high, int nNeed);
/**
*   find the k-th biggest element in a integer array, using a
*  modified quick sort algorithm.
*
*   Prarameters:
*   narray : the start address of the integer array.
*   n      : the size of the integer array.
*   k      : the priority of the needed element.
*
*   Return Value:
*   -1    : array size error.
*   -2    : k value invalid.
*   other : the index of the k-th biggest element in the array.
*/
int find_orderk(const int * narray, const int n, const int k) {
    if ( n < 1)
        return -1;
    if ( (K < 1) || (K > n) )
        return -2;
    // store a copy of the original int arrray.
    int * pN = new int[n];
    for (int i = 0; i < n; i++)
        pN[i] = narray[i];
    // find the k-th biggest VALUE in the int array.
    int nVal = new_qsort(pN, 0, n-1, k-1);
    // find the first position of the k-th biggest VALUE in the original array.
    for (int i = 0; i < n; i++)
        if ( narray[i] == nVal)
            return i;
};

/**
*   one pass of standard quik sort.
*
*   Parameters:
*       na    : the start address of the integer array.
*       low   : the lower boundary of the elements needed to be processed.
*       hight : the upper boundary of the elements needed to be processed.
*
*   Return Value:
*       the index of the pivot element after this pass.
*/
int partition(const int * na, int low, int hight) {
    int nTmp = na[low];
    while (low < high ) {
        while (low < high && na[high] <= nTmp)
            high--;
        na[low] = na[high];
        while (low < high && na[low] >= nTmp)
            low++;
        na[higt] = na[low];
    }
    na[low] = nTmp;
    return low;
}
/**
*       modified qsort, only sort the part that contains the
*  nNeed-th biggest element. The return value is the value of
*  the nNeed-th biggest element, not the position.
*
*   Parameters:
*       na    : the start address of the integer array.
*       low   : the lower boundary of the elements needed to be processed.
*       hight : the upper boundary of the elements needed to be processed.
*       nNeed : the priority of the needed element.
*
*   Return Value:
*       the value of the nNeed-th biggest element in the given integer array.
*/
int new_qsort(const int * na, int low, int high, int nNeed) {
    int nFound = partition(na, low, high);
    if (nFound == nNeed) {
        return na[nFound];
    } if (nFound < nNeed) {
        return new_qsort(na, nFound, high);
    } if (nFound > nNeed) {
        return new_qsort(na, low, nFound);
    }
}


Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=548753

阅读(1604) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~