这个算法看了半天没看明白机制，谁能解释一下具体实现过程
例如数据：L，8,7,9,3,5,4,2
L为头结点，只有指针域，没有数据域
void Sort(LinkList &L){
    //本算法实现将单链表L的结点重排，使其递增有序
    LNode *p=L->next, *pre;
    LNode *r=p->next;  //r保持*p后继结点指针，以保证不断链
    p->next=NULL;  //构造只含一个数据结点的有序表
    p=r;
    while(p!=NULL){
        r=p->next;  //保存*p的后继结点指针
        pre=L;
        while (pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;  //在有序表中查找插入的前驱结点*pre
        p->next=pre->next;  //将*p 插入到*pre 之后
        pre->next=p;
        p=r； //扫描原单链表中剩下的结点
    }
}

这个嘛~试试画图~我自己曾经写过类似的仿照冒泡法排序~要说解释有动态图解会方便很多~
到底总觉得自己说了很多不中用的~或者说我可以理解但表达过来的感觉自己也不怎么会理解了~到底还是喜欢自己理解去~

PS:可以试试记录一趟排序的指针指向变动以及变动顺序~

[此贴子已经被作者于2017-8-6 20:10编辑过]

这个是不带头节点的~当然带头节点的可以简单一些~可以对比参照一下~

Node* sort(Node* head)
{
    Node tnode={0};
    Node* p=&tnode;
    tnode.next=head;

    while (p->next)
    {
        Node* pt=p;

        while (pt->next)
            if (pt->next->n<p->next->n)
            {
                Node* tmp=pt->next->next;
                pt->next->next=p->next;
                p->next=pt->next;
                pt->next=tmp;
            }
            else
                pt=pt->next;

        p=p->next;
        
    }
    return tnode.next;
}

这种排序感觉有点别致~好像不是冒泡法排序~更加像插入排序~和数组的插入排序区别是不用变动整个数据~值得学习~

哇~利用链表特有的性质~感觉比我二楼曾经写的仿照冒泡法排序效率要高一些~赶紧记录一下~

[此贴子已经被作者于2017-8-6 20:26编辑过]

//这个算法看了半天没看明白机制，谁能解释一下具体实现过程
//例如数据：L，8,7,9,3,5,4,2
//L为头结点，只有指针域，没有数据域

#include<stdio.h>
#include<malloc.h>
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;
typedef LNode *LinkList;
void Show(LinkList &L) {
    LNode *p=L->next;
    while(p!=NULL){
        printf("%d,", p->data);
        p=p->next;
    }
    printf("\n");
}
void Sort(LinkList &L){
    //本算法实现将单链表L的结点重排，使其递增有序
    LNode *p=L->next, *pre;
    LNode *r=p->next;  //r保持*p后继结点指针，以保证不断链
    p->next=NULL;  //构造只含一个数据结点的有序表
    p=r;
    while(p!=NULL){
        r=p->next;  //保存*p的后继结点指针
        pre=L;
        while (pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;  //在有序表中查找插入的前驱结点*pre
        p->next=pre->next;  //将*p 插入到*pre 之后
        pre->next=p;
        p=r; //扫描原单链表中剩下的结点
           Show(L);
    }
}

main(){
    LinkList h = (LinkList)malloc(sizeof(LNode));
    LNode *p=h;
    int a[]={8,7,9,3,5,4,2};
    for(int i=0;i<7;i++){
        LNode *q = (LNode*)malloc(sizeof(LNode));
        q->data=a[i];
        q->next=NULL;
        p->next=q;
        p=q;
    }
    Sort(h);    
}

源数据:
8,7,9,3,5,4,2

结果:
7,8,
7,8,9,
3,7,8,9,
3,5,7,8,9,
3,4,5,7,8,9,
2,3,4,5,7,8,9,

--------------------------------
Process exited with return value 0
Press any key to continue . . .

分析:根据结果具有插入排序特征
原始数据:
8,7,9,3,5,4,2
代码:

    //截取链表L,从首元节点(8所在结点)开始 
    LNode *p=L->next, *pre;
    //保存首元节点下一个结点 
    LNode *r=p->next;
    //将首元节点的后继指向改为NULL,即L链表被切断,仅剩头结点和首元结点 
    //L:head->8 
    p->next=NULL;
    //p的指向更新为r的节点,即
    //p:7->9->3->5->4->2 
    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
        //第一轮:
            p:7->9->3->5->4->2 
            r:9->3->5->4->2
            pre:head->8 
        //第二轮:
            p:9->3->5->4->2 
            r:3->5->4->2
            pre:head->7->8
        while (pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;  //在有序表中查找插入的前驱结点*pre
        //第一轮:
            pre:head->8
                :head (pre->next->data:8,p->data:7    8>7跳出循环)
        //第二轮:
            pre:head->7->8
                :8 (pre->next==NULL,p->data:9    pre->next==NULL短路判断,跳出循环)
        p->next=pre->next;
        pre->next=p;
        p=r;
           Show(L);
           
        //第一轮:
            p:9->3->5->4->2 
            r:9->3->5->4->2
            pre:head->7->8
        
        //第二轮:
            p:9->3->5->4->2 
            r:9->3->5->4->2
            pre:head->7->8    
    }

大致流程就是说从r保存的子链表挨个取出每个结点
在L这个只有一个结点的链表不断的找到合适的位置插入r的每个结点

谢谢，写的非常详细，也很清楚。现在明白点了。