// 单链表通过移动 节点 实现数据的升序排序 大家给指出哪里错了，怎么改进下.. 假设数据类型为整型。
void sort(Linklist head)
{
    ListLnode *p,*rear,*r,*k；
         
        int min;
        rear=head;
                   p=head;   // 想法这样的 始终 保持 r 为 p 的前驱
        r=p;
        k=head->next; // k 指向第一个节点
        while(k)
        {  
            min=k->data;
            for(r=p,p=p->next;(r&&p);r=p,p=p->next)
            {
                if(min>p->data)
                   min=p->data;
            }
            if(min==k->data)   //j假如第一个节点经过遍历是最小的
            {   
                p=k;
                r=p;
                k=k->next;   // k向后移动 r和p 始终保持前驱和后继的关系

            }
            else
            {
                r->next=p->next;  // 取出最小的节点
                p->next=rear->next; // 插入到第一个节点的前面
                rear->next=p;
                rear=p;   // 这一步想着 rear 能够指向当前的最小值节点
                r=p;
                k=p->next; // k 继续向后移动 实现下一步遍历
            }

        }
   
}

我这里有个单链表排序

我没看出，这是个排序算法。太复杂了。

[ 本帖最后由 cosdos 于 2011-6-12 22:39 编辑 ]

我想知道 怎么错的，我想在自己的程序上改下.。。

失误了

[ 本帖最后由 cosdos 于 2011-6-12 22:48 编辑 ]

我的基本思想 是 遍历出最小的数据 节点插到最前面，然后继续遍历找到最小的 依次插到后面.....就是这样想的...你有好的算法？

失误啊

[ 本帖最后由 cosdos 于 2011-6-13 00:16 编辑 ]

void sort(QueueNode *head)
{
    QueueNode *i, *j, *min, *min_prev, *j_prev;
    if (head == NULL)
        return;
    i = head->next;
    head->next = NULL;
    for (i; i != NULL; )
    {
        min = min_prev = j_prev = i;
        for (j=i->next; j!=NULL; j=j->next)
        {
            if (min->data > j->data)
            {
                min = j;
                min_prev = j_prev;
            }
            j_prev = j;
        }
        if (min == i)
            i = i->next;
        min_prev->next = min->next;     // 移出链表
        min->next = NULL;               // 
        head->next = min;
        head = head->next;
    }
}

[ 本帖最后由 cosdos 于 2011-6-13 00:30 编辑 ]

通过测试

------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

void sort(QueueNode *head)
{
    QueueNode *i, *j, *min, *min_prev, *j_prev;
    if (head == NULL)
        return;
    i = head->next;
    head->next = NULL;
    for (i; i != NULL; )
    {
        min = min_prev = j_prev = i;
        for (j=i->next; j!=NULL; j=j->next)
        {
            if (min->data > j->data)
            {
                min = j;
                min_prev = j_prev;
            }
            j_prev = j;
        }
        if (min == i)
            i = i->next;
        min_prev->next = min->next;     // 移出链表
        min->next = NULL;               // 
        head->next = min;
        head = head->next;
    }
}

int main(void)
{
    int d;
    QueueNode QueueRoot, *p, *newnode;
    QueueRoot.next = NULL;
    p = &QueueRoot;
    
    while (scanf("%d", &d) == 1)
    {
        newnode = (QueueNode*)malloc(sizeof(QueueNode));
        newnode->data = d;
        newnode->next = NULL;
        p->next = newnode;
        p = p->next;
    }
    sort(&QueueRoot);
    
    for (p=QueueRoot.next; p != NULL; p=p->next)
    {
        printf("%d  ", p->data);
    }
    system("pause");
    return 0;
}

[ 本帖最后由 cosdos 于 2011-6-13 00:31 编辑 ]

很感谢，我好像知道，自己错到哪里了，我去修改下我写的....