【答案解析】最容易想到的排序算法是冒泡排序法，所以首先用冒泡排序法进行单链表的排序。程序示例如下：
#include＜stdio.h＞
#include＜stdlib.h＞
typedef struct node
int data;
struct node *next;
}linklist;
linklist *head=NULL;
linklist* CreateList(int* arr,int len)
{
int data;
linklist *pCurrent,*rear;
head=(linklist*)malloc(sizeof(linklist));
rear=head;
int count=0;
while(count＜len)
{
pCurrent=(linklist*)malloc(sizeof(linklist));
pCurrent-＞data=arr[count];
rear-＞next=pCurrent;
rear=pCurrent;
count++;
}
rear-＞next=NULL;
return head;
void ShowList(linklist *p)
{
while(p)
{
printf("%d",p-＞data);
p=p-＞next;
}
printf("/n");
}
void BubbleSortList(linklist *p)∥链表冒泡顺序
{
linklist *_temp=p-＞next;
linklist *_node=p-＞next;
int temp;
for(;_temp-＞next;_temp=_temp-＞next)
{
for(_node=p-＞next;_node-＞next;_node=_node-＞next)
{
if(node-＞data＞_node-＞next-＞data)
{
temp=_node-＞data;
node-＞data=_node-＞next-＞data;
_node-＞next-＞data=temp;
}
}
}
int main()
{
int array[]={3,4,5,1,2,-1,7};
CreateList(array,sizeof(array)/sizeof(array[0]));
BubbleSortList(head);
ShowList(head-＞next);
return 0;
}
程序输出结果：
-1 1 2 3 4 5 7
在各种排序算法中，冒泡排序并非最高效的。对链表这一特定数据结构而言，最好使用归并排序算法。而堆排序、快速排序这些在数组排序时性能非常好的算法，用在只能“顺序访问”的链表中却不尽如人意，但是归并排序却可以，它不仅保持了O(nlogn)的时间复杂度，而且它的空间复杂度也从O(n)降到了O(1)，除此之外，归并排序是分治法的实现。具体实现过程如下：
#include＜iostream＞
#define MAXSIZE 1024
#define LENGTH 8
using namespace std;
typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;
void Merge(SqList SR,SqList &TR,int i,int m,int n)
{
int j,k;
for(j=m+1,k=i;i＜=m&&j＜=n;++k)
{
if(SR.r[i]＜=SR.r[j])
TR.r[k]=SR.r[i++];
else
TR.r[k]=SR.r[j++];
}
while(i＜=m)
TR.r[k++]=SR.r[i++];
while(j＜=n)
TR.r[k++]=SR.r[j++];
void MSort(SqList SR,SqList &TR1,int s,int t)
{
int m;
SqList TR2;
if(s==t)
TR1.r[s]=SR.r[t];
else
{
m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR, TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}
}
void MergeSort(SqList &L)
MSort(L,L, 1,L.length);
int main()
{
int i;
SqList L={{0,49,38,65,97,76,13,27},LENGTH};
MergeSort(L);
for(i=1;i＜=L.length;i++)
cout＜＜L.r[i]＜＜" ";
cout＜＜endl;
return 0;
}
程序输出结果：
0 13 27 38 49 65 76 97