sort

经典算法－－单链表选择排序第一种：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
  printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void paixu(Linklist head)
{Linklist p,q,small;int temp;

for(p=head->next;p->next!=NULL;p=p->next)
{small=p;
for(q=p->next;q;q=q->next)
if(q->data<small->data)
  small=q;
if(small!=p)
{temp=p->data;
p->data=small->data;
small->data=temp;}
} printf("输出排序后的数字:\n");
output(head);
} void main()
{Linklist head;
int x,j,n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
printf("已排序的数字:\n");
paixu(head);
}
第二种：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("输入数字:\n");
for(i=n;i>0;i--)
{scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;}
r->next=NULL;
return head;
} Linklist selectsort(Node *g)
{ Node *p,*q,*t,*s,*h;
h=(Node *)malloc(sizeof(Node));
h->next=g;
p=h;
while(p->next->next!=NULL)
{
  for(s=p,q=p->next;q->next!=NULL;q=q->next)
   if(q->next->data<s->next->data)
    s=q;
  if(s!=q)
  {
   t=s->next;
   s->next=t->next;
   t->next=p->next;
   p->next=t;
  }
  p=p->next;
}
  g=h->next;
  free(h);
  return g;
} void output(Linklist head)
{Linklist p;
p=head->next;
do{
  printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
} void main()
{Linklist head;
int x,j,n;
printf("输入数字的个数(n):\n");
scanf("%d",&n);
head=creat(n);
printf("输出数字:\n");
output(head);
head=selectsort(head);
printf("已经排序的数字:\n");
output(head);
}

///////////////////////////
Insert_Sort(Node*head)功能：单链表的插入排序

参数描述：
  Node *head： 单链表的首指针

Insert_Sort(Node *head){
   Node *s,       //还未排序节点序列的首结点指针
              *p,       //链表遍历指针
              *pre,   //当前节点的前驱节点指针
              *op;    //本轮待插入节点
s = head->link;
head->link = NULL;//拆链操作,将原来的链表头节点改为s, 然后将head的后继节点置为NULL,形成两个新的链表.
while(s != NULL)
{
  for(op = s,p = head;p != NULL && p->data < op->data;pre = p,p = p->link);
  s = s->link;
  if(p == head)
   head = op;
  else
   pre->link =op;
  op->link = p;
}
}

/////////////////////////////////////////

这里给出了一种单链表插入排序的实现。另一种类似的实现参见《C算法（第一卷：基础、数据结构、排序和搜索）（第三版）》程序3-11。

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

typedef struct list LIST;
typedef LIST *link;

struct list
{
int item;
link next;
};

/*插入排序主例程*/

void InsertionSort(link h)
{
     link h1,h2,h3; /*h2用来指向需要插入的结点，h3用来指向h2的前一个结点*/
     for(h3=h,h2=h->next;h2!=NULL;)
    {
           h1=h; /*h1用来遍历寻找合适的插入位置*/
           for(;h1!=h2;h1=h1->next)
          {
                 if(h1->next->item > h2->item)/*如果找到，即把h2所指向的结点插到h1后面，然后跳出循环*/
                {
                   h3->next=h2->next;
                   h2->next=h1->next;
                   h1->next=h2;
                   h2=h3->next;
                   break; /*别忘了此处的break*/
                }
          }

          if(h1==h2)/*此处需要注意，只在h2所指结点不需要前插时，移动h2和h3*/
         {
              h2=h2->next;
              h3=h3->next;
         }
     }
}

/*单链表插入排序的测试例程*/

int main(void)
{

     /*构造一个包含头节点的单链表*/
     link head = malloc(sizeof *head);
     link p = head;
     int i=0;
     while(i<100)
    {
         p->next = malloc(sizeof *head);
         p = p->next;
         p->item = rand()%100;
         printf("%d ",p->item);
         p->next = NULL;
         i++;
    }

    printf("\n");


    /*插入排序*/
    InsertionSort(head);


    /*输出排序后的链表*/
    p=head->next;
    while(p!=NULL)
   {
       printf("%d ",p->item);
       p=p->next;
   }

   /*释放内存*/
    while(head)
   {
    p=head;
    head=head->next;
    free(p);
   }

  

    return 0;
}