4,1,1,1,1,4
对这组数jack10141的解法得到的结果是错的，不相邻不能说明只能隔一个数的吧。

好像是你搞错了吧？jack10141的解法我觉得没有问题
如果按你说的他只隔一个数，那他何必用二重循环呢？

[ 本帖最后由 liqinm 于 2010-9-9 19:34 编辑 ]

对是我错了

10楼的思路不错

这个问题，可以证明，题目中最大的和由前4大（假设分别为A，B，C，D）就完全可以确定！！

题目中最大的和 必在  A+B  A+C  A+D  B+C   之内！！

说错了，

[ 本帖最后由 BlueGuy 于 2010-9-11 11:59 编辑 ]

选择排序适合在 m (m很大) 个元素中 找 前n个最大的数，(n很小)。
时间复杂度为 mn, 近似于线性。

[ 本帖最后由 BlueGuy 于 2010-9-11 17:34 编辑 ]

#include <stdio.h>

typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define more(A, B) (key(A) > key(B))
#define exch(A, B) {Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, B)

int main(void)
{
    int a[10] = {1, 3, 8, 7, 9, 9, 4, 6, 8, 10};
    int i, j, max;

    for (i = 0; i < 4; i++)
    {
        max = i;
        for(j = i + 1; j <= 10-1; j++)
        {
            if(more(a[j], a[max]))
                max = j;
        }
        exch(a[i], a[max]);
    }
   
    for (i = 0; i < 4; i++)
    {
        printf("%d ", a[i]);
    }
    getchar();
    return 0;
}


[ 本帖最后由 BlueGuy 于 2010-9-11 12:26 编辑 ]

顺便说下， 选择排序还有一个重要的应用是在元素很大、关键字很小的时候， 此时选择排序也是 线性的。