Chinaunix首页 | 论坛 | 博客
  • 博客访问: 359195
  • 博文数量: 60
  • 博客积分: 15
  • 博客等级: 民兵
  • 技术积分: 1138
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-20 16:18
个人简介

最多140个字

文章分类

全部博文(60)

文章存档

2016年(1)

2015年(34)

2014年(25)

分类: C/C++

2015-03-21 13:06:09


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

  3. typedef struct list{
  4.     int data;
  5.     struct list *next;
  6. }list;

  7. void swap(int *a,int *b)
  8. {
  9.     int temp=*a;
  10.     *a=*b;
  11.     *b=temp;
  12.     return;
  13. }

  14. list* partition(list *head, list *tail)
  15. {
  16.     list *i=head;
  17.     list *j=head->next;
  18.     int mid=head->data;
  19.     while(j!=tail)
  20.     {
  21.         if(mid > j->data)
  22.         {
  23.             i=i->next;
  24.             swap(&(i->data),&(j->data));
  25.         }
  26.         j=j->next;
  27.     }
  28.     swap(&(i->data),&(head->data));
  29.     return i;
  30. }

  31. void quicksort(list *head, list*tail)
  32. {
  33.     if(head!=tail)
  34.     {
  35.         list *mid=partition(head,tail);
  36.         quicksort(head,mid);
  37.         quicksort(mid->next,tail);
  38.     }
  39. }

  40. list *createlist(int n)
  41. {
  42.     int i;
  43.     list *head=NULL;
  44.     list *p=NULL;
  45.     for(i=0;i<n;i++)
  46.     {
  47.         list *temp=(list*)malloc(sizeof(list));
  48.         temp->data=n-i;
  49.         temp->next=NULL;
  50.         if(head==NULL)
  51.         {
  52.             head=temp;
  53.             p=temp;
  54.         }
  55.         else
  56.         {
  57.             p->next=temp;
  58.             p=p->next;
  59.         }
  60.     }
  61.     return head;
  62. }

  63. void show(list *head)
  64. {
  65.     list *p=head;
  66.     while(p!=NULL)
  67.     {
  68.         printf("%d ",p->data);
  69.         p=p->next;
  70.     }
  71.     printf("\n");
  72.     return;
  73. }

  74. int main()
  75. {
  76.     list *head=createlist(15);
  77.     show(head);
  78.     quicksort(head,NULL);
  79.     show(head);
  80. }

阅读(2253) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~