多少得有点彩头才有动力嘛.你这帖连 1 分都不给,也太有点铁公鸡了吧.

收到的鲜花

• missiyou 于 2010-03-05 14:01 送鲜花  33朵   附言：给你太多分，你就成了砖家了

贴一个 权当抛砖引玉好了

写完才发现 要求 用链表实现
听楼主的话好像链表能优化,  我是想不明白..

#include <stdio.h>
#include <stdlib.h>
//对数组arr从下标left到right以arr[left]划分
//从大到小
int partition(int arr[], int left, int right)
{
    int key = arr[left];
    while(left < right)
    {
        //从right往左找到第一个大于 x 的数, 填到arr[left]中
        while (left < right && arr[right] <= key)
            right--;
        arr[left] = arr[right];
        //从left往右找到第一个小于 x 的数, 填到arr[right]中
        while (left < right && arr[left] >= key)
            left++;
        arr[right] = arr[left];
    }
    arr[left] = key;
    return left;
}
//得到数组中第k大的数
int getKmaxNum(int arr[], int size, int k)
{
    //第k大的数在降序排列的数组中下标为 k-1
    k--;
    int left = 0, right = size - 1, pos;
    for ( ; ;)
    {
        pos = partition(arr, left, right);
       
        if (pos == k)
            break;
        if (pos > k)
        {
            right = pos - 1;
        }   
        else
        {
            left = pos + 1;
            k -= pos;
        }
    }
    return arr[pos];
}
int _tmain(int argc, _TCHAR* argv[])
{
    int arr[6] = {332,32,1,3,5,6};
    printf("%d\n", getKmaxNum(arr, 6, 2));
    return 0;
}

[ 本帖最后由 jimmywood 于 2010-3-3 17:18 编辑 ]

int partition(int arr[], int left, int right)
{
    int key = arr[left];
    while(left < right)
    {
        //从right往左找到第一个大于 x 的数, 填到arr[left]中
        while (left < right && arr[right] <= key)
            right--;
        arr[left] = arr[right];
        //从left往右找到第一个小于 x 的数, 填到arr[right]中
        while (left < right && arr[left] >= key)
            left++;
        arr[right] = arr[left];
    }
    arr[left] = key;
    return left;
}

你非得用一个3个while吗？

你绝不绝望和我们有关系？

新手怎么了 谁不是新手过来的 就你是被外星人ooxx了一出生就会编程？

哎 不想多说 你要么贴代码 要么闪一边凉快去

int partition(int arr[], int left, int right)
{
    int pivot = arr[left], i, j;
    i = j = left;
    while (j <= right)
    {
        if (a[j] <= pivot)
        {
            swap(&a[i], &a[j]);
            i++;
            j++;
        }
        else
            j++;
    }
    swap(&a[i - 1], &a[left]);
    return left;
}

用链表结构写写看呢。

失望了就滚，

整天唧唧歪歪。

无知者，无畏。

贴代码吧~~~要么就沉算了。。

其实用数组链表就可以了，不要被链表那个不能定位所困。数组有标识，就是结构数组链表。利用数组标识直接定位，可以 实现 O(1)查找。

如果是事先排序的，就更好。要不是就是哈希链表，其实也还是链表。只是处理方式不同而以。

我们可以用数组迅速定位，也可以按链表方式遍历。数组的打乱，不会影响链表的遍历。

[ 本帖最后由 missiyou 于 2010-3-5 13:58 编辑 ]