函数LinkSort是怎么实现排序的，用的是什么排序

Question

#include
using namespace std;
class Node //结点类
{ public:
Node( );
Node(int ); //构造函数
void SetNext(Node *p); //设置后继结点
int Getd();
void Setdata(int); //得到当前结点的数据值
Node *GetNext( ); //得到后继结点的地址
~Node( ); //析构函数
private:
int data;
Node *next;
};
Node::Node( )
{ }
Node::Node(int d):data(d)
{

}
void Node::SetNext(Node p)
{ next=p;}
int Node::Getd( )
{ return data;}
Node Node::GetNext( )
{ return next;}
void Node::Setdata(int n)
{
data=n;
}
Node::~Node( )
{ cout<<data<<" 被析构！"<<endl;}

class Link
{
public:
Link();
Link(int n);
void LinkPrint();
void LinkSort();
void LinkInsert(int);
void LinkDel(int);
//void con(Link*);
void operator+(Link&);
~Link();
private:
Node *Head;
int num;
};

Link::Link():num(0),Head(NULL)
{

}

Link::Link(int n):num(n)
{
Node *h=NULL,*p,*q;
int d;
int i;
if(n>0)
{
cin>>d;
h=q=p=new Node(d);
for(i=2;i<=num;i++)
{
cin>>d;
p=new Node(d);
q->SetNext(p);
q=p;
}
q->SetNext(NULL);
}
Head=h;
}

void Link::LinkPrint()
{
Node *p;
p=Head;
while(p)
{
cout<Getd()<<" ";
p=p->GetNext();
}
cout<<endl;
}

void Link::LinkSort()
{

Node *h1,*h2;
Node *p,*q,*t;
h2=h1=Head;
h2=h2->GetNext();
h1->SetNext(NULL);
for(;h2;)
{
    t=h2;
    for(p=h1,q=p;(q)&&(t->Getd()>q->Getd());p=q,q=q->GetNext());
    h2=h2->GetNext();
    if(q==h1)
    {
        t->SetNext(q);
        h1=t;
    }
    else
    {
        p->SetNext(t);
        t->SetNext(q);
    }
}
Head=h1;

}

void Link::LinkInsert(int d)
{
Node *p,*q,*s;
p=q=Head;

while(q&&(d>q->Getd()))
{
    p=q;
    q=q->GetNext();
}
s=new Node(d);
if(q==Head)
{
    s->SetNext(q);
    Head=s;
}
else
{
  s->SetNext(q);
  p->SetNext(s);
}

}

void Link::LinkDel(int d)
{
Node *p,*q;
p=q=Head;

while(q&&(d!=q->Getd()))
{
    p=q;
    q=q->GetNext();
}
if(q==NULL)
{
    cout<<"不存在此数据!"<<endl;
    return ;
}
if(q==Head)
{
    Head=Head->GetNext();
    delete q;
}
else
{
    p->SetNext(q->GetNext());
    delete q;
}

}

void Link::operator+(Link&l)
{
Node *p;
p=Head;
while(p->GetNext())
{
p=p->GetNext();
}
p->SetNext(l.Head);
l.Head=NULL;
}
Link::~Link()
{
Node *p,*q;
p=Head;
while(p)
{
q=p->GetNext();
delete p;
p=q;
}

}

main()
{
//Link l1(5);
Link *p,q;
p=new Link(5);
/
p->LinkPrint();
p->LinkSort();
p->LinkPrint();
p->LinkInsert(15);
p->LinkPrint();
p->LinkDel(15);
p->LinkPrint();
*/
q=new Link(3);
//p->con(*q);
*p+*q;
p->LinkPrint();
delete p;
delete q;
}

Answer 1

很明显，这是插入排序。

void Link::LinkSort()
{
    Node* h1, * h2;
    Node* p, * q, * t;
    h2 = h1 = Head;
    h2 = h2->GetNext();
    h1->SetNext(NULL);

    //h1的初始值是第一个节点；h2的初始值是第二个节点
    //可以把h1看做一个已排序链表，h2看做一个未排序的链表

    //对h2进行遍历
    for (; h2;)
    {
        t = h2;
        //这个for循环是关键
        //p的初始值是已排序链表，q的初始值是p
        //t的初始值是未排序链表的首节点
        //for循环结束条件单,t的值大于q的值，或者q为空（遍历完已排序链表）
        //for循环的迭代:q往后移一个节点
        //for循环之后，要么t的值大于q的值，要么t的值大于所有已排序链表的值（q为空）
        for (p = h1, q = p; (q) && (t->Getd() > q->Getd()); p = q, q = q->GetNext());
        h2 = h2->GetNext();
        if (q == h1)
        {
            t->SetNext(q);
            h1 = t;
        }
        else
        {
            p->SetNext(t);
            t->SetNext(q);
        }
    }
    Head = h1;
}