首页 > 基础算法 > 排序 > 归并排序对链表进行排序
2014
03-24

归并排序对链表进行排序

归并排序通常是链表排序的第一选择。由于无法对链表随机访问,快速排序的的效果并不好,堆排序也是无法实现的。

为了和大部分数据结构中的链表结构保持一致,head表示链表的头节点,headRef表示指向头节点(head)的指针。注意,我们需要一个指针指向头节点MergeSort()中,因为以下实现将更改next,所以头节点必须改变如果原始数据头不是链表中的最小值。

MergeSort(headRef)
1) If head == NULL or 只有一个元素
    then return.
2) Else 将链表分为两个部分  
      FrontBackSplit(head, &a, &b); /* a,b分别代表分割后的链表 */
3) 分别对a,b排序
      MergeSort(a);
      MergeSort(b);
4) 合并已排序的a,b ,并跟新 头指针headRef
     *headRef = SortedMerge(a, b);

代码实现:

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

struct node
{
    int data;
    struct node* next;
};

/* 函数定义 */
struct node* SortedMerge(struct node* a, struct node* b);
void FrontBackSplit(struct node* source,
          struct node** frontRef, struct node** backRef);

/* 通过改变指针来排序,而不是数据 */
void MergeSort(struct node** headRef)
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;

  if ((head == NULL) || (head->next == NULL))
  {
    return;
  }

  /* 分割链表为 'a' 和  'b' 两个子链表 */
  FrontBackSplit(head, &a, &b); 

  MergeSort(&a);
  MergeSort(&b);

  /* 记得跟新头指针 */
  *headRef = SortedMerge(a, b);
}

/* 合并两个已排序链表 */
struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);
  /* 使用递归调用的方法 */
  if (a->data <= b->data)
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}

/* 公用函数 */
/* 分割一个链表为两部分,通过指针返回结果,使用快慢指针  */
void FrontBackSplit(struct node* source,
          struct node** frontRef, struct node** backRef)
{
  struct node* fast;
  struct node* slow;
  if (source==NULL || source->next==NULL)
  {
    /* length < 2 */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->next;

    /* 'fast'移动两个节点,  'slow' 移动一个节点 */
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }

    /* 'slow' 在中间位置的前面 */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}

/* 打印链表 */
void printList(struct node *node)
{
  while(node!=NULL)
  {
   printf("%d ", node->data);
   node = node->next;
  }
}

/* 插入数据 */
void push(struct node** head_ref, int new_data)
{
  struct node* new_node =
            (struct node*) malloc(sizeof(struct node));

  new_node->data  = new_data;
  new_node->next = (*head_ref);    
  (*head_ref)    = new_node;
} 

/* 测试程序 */
int main()
{
  struct node* res = NULL;
  struct node* a = NULL;

  /* 创建一下链表 a: 2->3->20->5->10->15 */
  push(&a, 15);
  push(&a, 10);
  push(&a, 5); 
  push(&a, 20);
  push(&a, 3);
  push(&a, 2); 

  MergeSort(&a);

  printf("\n Sorted Linked List is: \n");
  printList(a);           

  getchar();
  return 0;
}

参考:http://www.geeksforgeeks.org/merge-sort-for-linked-list/


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }