- #include <stdlib.h>
- #include <stdio.h>
- typedef struct node {
- int data;
- struct node* next;
- }node;
- void print_list(node* head){
- node* p = head->next;
- while(p){
- printf("%d ", p->data);
- p = p->next;
- }
- printf("\\n\\n");
- }
- void merge_sort_list(node* head){
- node *p, *q, *cur;
- int s=1, sp=s, sq=s, lq=s;
- node* nhead = (node*)malloc(sizeof(node));
- nhead->next = head->next;
- while(1){
- print_list(nhead);
- cur = nhead;
- p = nhead->next;
- q = p;
- while(q && lq--)
- q = q->next;
- if(!q)
- break;
- while(1){
- while(sp && sq && p && q){
- if(p->data < q->data){
- cur->next = p;
- cur = p;
- p = p->next;
- sp--;
- }else{
- cur->next = q;
- cur = q;
- q = q->next;
- sq--;
- }
- }
- while(sp-- && p){
- cur->next = p;
- cur = p;
- p = p->next;
- }
- while(sq-- && q){
- cur->next = q;
- cur = q;
- q = q->next;
- }
- cur->next = q;
- if(cur->next==NULL)
- break;
- p = cur->next;
- q = p;
- sp = s;
- sq = s;
- lq = s;
- while(q && lq--)
- q = q->next;
- if(!q) break;
- }
- s += s;
- sp = s;
- sq = s;
- lq = s;
- }
- head->next = nhead->next;
- }
- int main(){
- int num[] = {34,5, 20, 7,2,1, 8, 17,19,11,90,18, 28};
- int i;
- node* head = (node*)malloc(sizeof(node));
- node* p = head;
- for(i=0;i<sizeof(num)/sizeof(int);i++){
- node* n = (node*)malloc(sizeof(node));
- n->next = NULL;
- n->data = num[i];
- p->next = n;
- p = n;
- }
- merge_sort_list(head);
- print_list(head);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/040520149440.html
来源: http://www.codesnippet.cn/detail/040520149440.html