怎样实现链表的归并排序

  #返回上一级

@Author: 张海拔

@Update: 2014-01-27

@Link: http://www.cnblogs.com/zhanghaiba/p/3534521.html

 

链表不像数组通过计算来随机存取,高效的排序算法如快速排序、堆排序都比较难实现,而归并排序就适合给链表排序。

在"有序单链表的合并 link(public)"问题中,我对带头结点和不带头结点的 有序单链表的合并算法做了比较全面的介绍。

而且知道就地合并算法比数组的合并算法时间效率更好,而且空间复杂度完胜,是O(1)(不然怎么叫就地)。

 

我们已经熟悉数组的“归并排序 link(public) ”,链表的归并排序用到的归并算法肯定是一样的,是典型的分治(二分)过程。

还是先给出伪代码:

merge_sort()

{

if 元素只有一个(已经有序)

  return;

划分为左右两段

对左段进行merge_sort()

对右段进行merge_sort()

//此时左段和右端已经有序

对左段和右段进行sorted_merge()

}

sorted_list_merge()我们已经实现过了,merge_sort的思路也清晰了,剩下的问题,怎样把一段链表划分为两段

链表的追及问题其实挺经典的,比如“链表是否有环”和“确定链表倒数第K个元素”,这样的问题都是用到追击(相对速度)的思路。

这里也一样,使用一个slow指针和一个fast指针,让fast指针相对slow指针的移动速度是单位1。这样fast走到尽头时,slow就在“中间”位置了。

这个时候需要考虑一些边界问题。

只有一个元素时,merge_sort()直接返回(已经有序,不用再处理),不再划分。

那么只有两个元素的情况对应划分的最小子问题——

首先,直接让slow初始指向first,而fast初始指向first->next,

然后每次前进让fast先后一步再验证是否到边界,若没有则fast和slow都走一步。

这样初始化后,fast走一步后发现到了边界,slow便不走,还是指向first。

将左段链表的首节点指针left = first,右段链表的首节点指针right = slow->next,然后切断原链表,即slow->next = NULL;

对于最小子问题这样划分是正确的(left指向第一个节点,right指向第二个节点)。

由于fast相对slow速度为1,且最小子问题也正确,对于更大的子问题,不管划分边界是[n/2]取上界还是下界问题都不大。

 

所以,这个算法时间复杂度仍然是O(n*lgn),空间复杂度O(1)

数组的归并排序合并过程需要来回两次循环复制即2*O(n),而链表的归并排序是划分过程仅需要循环一次1*O(n)。

两者递归的深度是一样的(都是二分)。

综合来看,链表归并排序的时间复杂度系数应该更低,即理论上会比数组归并排序更快。

 

 

下面给出链表归并排序的完整实现——

其中:

sorted_list_merge()是递归实现的

sorted_list_mrege2()是迭代实现的

list_merge_sort()接受带头结点的单链表,返回也是带头结点的单链表

list_merge_sort_core()接受不带头结点的单链表,返回的也是不带头结点的单链表

显然list_merge_sort()包装一下list_merge_sort_core()即可实现。

默认支持带头结点的单链表是考虑到问题集的其它链表都是带头结点的,而不带头结点适用性更强,实现了后者,前者只需简单包装就能实现。

另外约定:带头结点的单链表的头结点指针命名为head,而不带头结点的单链表的第一个结点(首节点)指针命名为first。带头节点的单链表的第一个有效元素的指针也叫first。

 

怎样实现链表的归并排序
  1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-26
  4  *File: merge_sort_for_singly_linked_list.c
  5  *
  6  *a demo shows merge sort for singly_linked_list
  7  */
  8 
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 #define INF 0x7fffffff
 12 
 13 typedef struct node * link;
 14 typedef struct node {
 15     int item;
 16     link next;
 17 }node;
 18 
 19 //public
 20 /*
 21  *recieve a singly linked list with Head Node and
 22  *return a singly linked list with Head Node as well
 23  */
 24 link list_merge_sort(link list_head);
 25 link NODE(int item, link next);
 26 link list_create(int n);
 27 void list_travel(link head);
 28 void list_destroy(link head);
 29 
 30 //private
 31 /*recieve a singly linked list without Head Node and
 32  *return a singly linked list without Head Node as well
 33  */
 34 link list_merge_sort_core(link list_first);
 35 void list_divide(link src_list, link *left_list, link *right_list);
 36 link sorted_list_merge_in_place(link src_list_a, link src_list_b);  //recusive
 37 link sorted_list_merge_in_place2(link src_list_a, link src_list_b); //iterative
 38 
 39 
 40 int main(void)
 41 {
 42     int n;
 43 
 44     scanf("%d", &n);
 45     link list_a = list_create(n);
 46     printf("before merge sort, travel:\n");
 47     list_travel(list_a);
 48     list_a = list_merge_sort(list_a);
 49     printf("after merge sort, travel:\n");
 50     list_travel(list_a);
 51     list_destroy(list_a);
 52     return 0;
 53 }
 54 
 55 link list_merge_sort(link head)
 56 {
 57     if (head == NULL) //if [list with Head Node] have not Head Node
 58         return NULL;
 59     return NODE( INF, list_merge_sort_core(head->next) );
 60 }
 61 
 62 link list_merge_sort_core(link first) //first node pointer
 63 {
 64     link left, right;
 65 
 66     if (first == NULL || first->next == NULL)
 67         return first;
 68     list_divide(first, &left, &right);
 69     left = list_merge_sort_core(left);
 70     right = list_merge_sort_core(right);
 71     return sorted_list_merge_in_place2(left, right);
 72 }
 73 
 74 //guarantee first != NULL
 75 void list_divide(link first, link *left, link *right)
 76 {
 77     link slow = first, fast = first->next;
 78 
 79     while (fast != NULL) {
 80         fast = fast->next;
 81         if (fast != NULL) {
 82             fast = fast->next;
 83             slow = slow->next;
 84         }
 85     }
 86     *left = first;
 87     *right = slow->next;
 88     slow->next = NULL;
 89 }
 90 
 91 link sorted_list_merge_in_place(link left, link right)
 92 {
 93     if (left == NULL)
 94         return right;
 95     if (right == NULL)
 96         return left;
 97     link first = NULL;
 98     if (left->item <= right->item) {
 99         first = left;
100         first->next = sorted_list_merge_in_place(left->next, right);
101     } else {
102         first = right;
103         first->next = sorted_list_merge_in_place(left, right->next);
104     }
105     return first;
106 }
107 
108 link sorted_list_merge_in_place2(link left, link right)
109 {
110     link tmp_head = NODE(INF, NULL);
111     link first = tmp_head;
112 
113     for (; left != NULL && right != NULL; first = first->next) {
114         if (left->item <= right->item)
115             first->next = left, left = left->next;
116         else
117             first->next = right, right = right->next;
118     }
119     first->next = left != NULL ? left : right;
120     first = tmp_head->next;
121     free(tmp_head);
122     return first;
123 }
124 
125 
126 link NODE(int item, link next)
127 {
128     link born = malloc(sizeof (node));
129     born->item = item;
130     born->next = next;
131     return born;
132 }
133 
134 //tail insert
135 link list_create(int n)
136 {
137     int i, item;
138     link head = NODE(INF, NULL);
139     link tail = head;
140 
141     for (i = 0; i < n; ++i) {
142         scanf("%d", &item);
143         tail->next = NODE(item, NULL);
144         tail = tail->next;
145     }
146     return head;
147 }
148 
149 void list_travel(link head)
150 {
151     for (head = head->next; head != NULL; head = head->next)
152         printf(head->next == NULL ? "%d\n" : "%d ", head->item);
153 }
154 
155 void list_destroy(link head)
156 {
157     head->next == NULL ? free(head) : list_destroy(head->next);
158 }
怎样实现链表的归并排序

 

测试示范:

怎样实现链表的归并排序
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
1
435
before merge sort, travel:
435
after merge sort, travel:
435
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
9
4324 31 515 41 46 43 8 53 3    
before merge sort, travel:
4324 31 515 41 46 43 8 53 3
after merge sort, travel:
3 8 31 41 43 46 53 515 4324
怎样实现链表的归并排序

 

 

   #返回上一级

怎样实现链表的归并排序

上一篇:表的多条记录合并成一条记录


下一篇:财经投资简报 2014 -1-27