爱华网#include <iostream>
using namespace std;
#define SIZE100//链表容量
typedef struct
{
intrc;//数据项
intnext;//指针
} SLNode;
typedef struct
{
SLNoder[SIZE];//静态数组
intlength;//链表的当前长度
} SLinkList;
void CreateList(SLinkList &SL)
{
int i, p, k;
SL.r[0].rc = INT_MAX;
SL.r[0].next = 1;
SL.r[1].next = 0;
// 以第一个和第0个数据项构成一个循环链表
for(i = 2; i <= SL.length;i++)
{
p =SL.r[0].next;//p是当前SL.r[i]的next域的值
k =0;//k用开保存当前的位置
if(SL.r[i].rc <SL.r[p].rc)
{
//当前的节点比已排好序的所有节点都要小
SL.r[i].next= p;
SL.r[k].next= i;
}
else
{
while(1)
{
intt = SL.r[p].next;
if(SL.r[i].rc>= SL.r[p].rc &&SL.r[i].rc < SL.r[t].rc)
break;
k= p;
p= SL.r[p].next;
}
SL.r[i].next = SL.r[p].next;
SL.r[p].next= i;
}
} // for
}
void Arrage(SLinkList &SL)
{
int p, i, q;
p =SL.r[0].next;//p指示第一个记录的当前位置
for(i = 1; i < SL.length;i++)
{
while( p <i)p =SL.r[p].next;//找到第i个记录，并用p指示其在SL中的当前位置
q =SL.r[p].next;//q指示下一个将要调整的记录
if( p != i)
{
// 交换记录
SLNodetemp;
temp =SL.r[p];
SL.r[p] =SL.r[i];
SL.r[i] =temp;
SL.r[i].next =p;//指向交换前的记录，一边以后的while循环找到该记录
}
p =q;//p指向尚未调整的记录
}
}
void main()
{
SLinkList SL;
int i;
scanf("%d", &SL.length);
for(i = 1; i <= SL.length;i++)
{
scanf("%d",&SL.r[i].rc);
SL.r[i].next =-1;//-1代表不指向任何数据
}
CreateList(SL);
Arrage(SL);
for(i = 0; i <= SL.length;i++)
{
printf("%d %dn", SL.r[i].rc,SL.r[i].next);
}
}
