谈谈归并排序算法
2018-08-06
谈谈归并排序算法
归并排序算法是一个很重要的算法。在排序算法中，算是非常重要的一个算法。我们常说的数组归并排序，是指二路归并排序算法，时间复杂度是O(nlog(n)),空间负责度是O(n).核心的思想就是对两个有序数组合并成一个有序数组。对于一个未排序的数组怎么产生两个已排序的数组呢？其实就是对数组不断的分割，分割成多个只有一个元素的数组。只有一个元素的数组，当然这个数组就是有序的了。然后再将这些数组进行两两合并，合并后的数组还是有序数组，这样再次进行两两合并，最终可以合并成一个有序数组，这样排序就完成了。
归并排序的算法看起来不是很复杂，但是实现起来我觉得不是那么简单。首先它需要额外的空间，这个额外的空间怎么分配跟算法实现方式有关。然后算法的实现方式有递归方式和迭代方式两种。网上流行的都是递归方式。
递归方式
递归方式采用典型算法：分治法来进行。
- 1.将数组分为两半，前一半和后一半。
- 2.将这两半进行有序数组合并
- 3.继续进行第1步，直到数组不能在分为止
这里明显采用了递归定义，递归定义其实不是那么好理解，也不是那么难理解。简单来说就是不断的将一个数组进行对半分，一直分到不能分为止，这样最终就会分得很多个元素个数为1的数组，然后再将这些数组进行两两合并。注意子数组可能是奇数个，但是这也没关系，没得合并的就暂时放在原位，下一次合并的时候总会用到，最终一个会合并成一个数组。
伪代码：
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
伪代码来源：geeksforgeeks
这里特意提一下geeksforgeeks这个网址，这里专门讲算法的网站，很多算法有解析和实现，而且基本都有c和Java的实现，甚至Python。非常有用的网站。
我的实现代码：
#include <stdlib.h>
void _sorted_merge(int a[], int start, int mid, int end) {
int len_l = mid - start + 1;
int len_r = end - mid;
int *arr_l = (int *)malloc(sizeof(int)*len_l);
int *arr_r = (int *)malloc(sizeof(int)*len_r);
for (int i=0; i<len_l; i++) {
arr_l[i] = a[start+i];
}
for (int i=0; i<len_r; i++) {
arr_r[i] = a[mid+i+1];
}
int i = 0;
int j = 0;
int k = start;
while (i < len_l && j < len_r) {
if (arr_l[i] <= arr_r[j]) {
a[k++] = arr_l[i++];
} else {
a[k++] = arr_r[j++];
}
}
while (i < len_l) a[k++] = arr_l[i++];
while (j < len_r) a[k++] = arr_r[j++];
free(arr_l);
free(arr_r);
}
void _recursive_merge_sort(int a[], int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
_recursive_merge_sort(a, start, mid);
_recursive_merge_sort(a, mid+1, end);
_sorted_merge(a, start, mid, end);
}
}
void recursive_merge_sort(int a[], int n) {
if (a == 0 || n <= 1) return;
_recursive_merge_sort(a, 0, n-1);
}
这里整个完整的实现是用了3个方法。暴露给外界使用的方法是 void recursive_merge_sort(int a[], int n)这个。递归分割数组是void _recursive_merge_sort(int a[], int start, int end)这个方法。注意方法参数是数组指针，要分割的开始坐标，要结束分割的坐标。另外核心的合并方法有序数组的方法是void _sorted_merge(int a[], int start, int mid, int end)。注意这里并不是传了两个数组进去，而是一个数组，给定了起始，中间分割，结束的坐标。中间分割坐标是归并在前一部分的。这些都是细节，没有搞清楚，程序就会出错。
在_sorted_merge这个方法内，新建了两个数组，将两半的元素拷贝到这两个数组中，然后合并到原始数组中。归并排序需要的额外空间是在这里花费的。这个算法实现完全是采用的是自顶向下的思维方式。一层一层的从顶往下分割，分割到最后在合并。
还有一种方式就是自底向上的思维方式。我们知道数组是可以随机访问的，因为坐标可以随时利用。如果一开始我们就只针对一个个的元素，那么这些元素就已经是独立的，换句话说就是已经分别好的。我们就针对每一个个体，直接跟它傍边的元素进行两两合并就好了。
迭代方式
迭代的方式就是把上面的void _recursive_merge_sort(int a[], int start, int end)这个方法换成循环迭代来实现。
void iteractive_merge_sort(int a[], int n) {
if (a == 0 || n <= 1) return;
int step = 1;
while (step < n) {
int start = 0, mid = 0, end = 0;
while (start < n-1) {
mid = start + step - 1;
end = mid + step;
if (end > n-1) end = n-1;
_sorted_merge(a, start, mid, end);
start += 2*step;
}
step = 2*step;
}
}
迭代方式定义了一个step,这个是需要合并的子数组的长度，初始化为1，这样就不能分割数组，直接合并就好。步长每次翻倍，最终步长超出数组长度就退出。这里也有很多细节要注意，定了步长之后，要对整个数组按照这个步长分成多个子数组来合并，这里要注意最后一个子数组的元素个数可能个数不够，不能超过数组总长。
另一种迭代方式
我们这里的有序数组合并都是在在_sorted_merge这个方法内实现的，空间分配也在这。这个方法会被频繁调用。空间会被进行很多次分配和释放。在我大学的数据结构的课本里，归并排序采用的并不是上面的方法，而是采用了另外一种迭代方法来实现。
先上代码：
void _merge_array(int a[], int b[], int n, int step) {
int k = 0;
int start1 = 0;
int end1, start2, end2;
while (k < n) {
end1 = start1 + step;
start2 = end1;
end2 = start2 + step;
if (end2 > n) end2 = n;
while (start1 < end1 && start2 < end2) {
if (a[start1] <= a[start2]) {
b[k++] = a[start1++];
} else {
b[k++] = a[start2++];
}
}
while (start1 < end1) b[k++] = a[start1++];
while (start2 < end2) b[k++] = a[start2++];
start1 = end2;
}
}
void iteractive_merge_sort2(int a[], int n) {
if (a == 0 || n <= 1) return;
int *b = (int *)malloc(sizeof(int)*n);
int flag = 0;
for (int i = 1; i<n; i=i*2) {
if (flag == 0) {
_merge_array(a, b, n, i);
flag = 1;
} else {
_merge_array(b, a, n, i);
flag = 0;
}
}
if (flag == 1) {
for (int i=0; i<n; i++) a[i] = b[i];
}
free(b);
}
在void iteractive_merge_sort2(int a[], int n)这个方法中，直接申请了一个跟原始数组一样大小的空间，然后后面的数组的合并算法就在这两个数组之间进行。当然最后如果最终结果被合并到了b数组中的话，就把它拷贝到原始的a数组中。而核心的数组合并在void _merge_array(int a[], int b[], int n, int step)这个方法中。它接收两个数组，第一位原始数组，第二个为合并后的数组。他们的数组大小一样，还有一个关键参数是步长。这个步长就是分割好的已有序数组的元素个数。里面的实现细节还是数组的下标，不能超过总数组长度。 这个方法的特别之处就是它是一次性分配内存的。这个说是好还是不好呢，我也不太敢确定。但是感觉他的效率要高些，因为不用频繁分配和释放内存。
链表的排序
大家都很清楚数组的排序有很多种，方法各异，但是不知道你想过没有，链表是怎么排序的。链表因为只能顺序访问，不能想数组那样随机访问，所以基本上数组的排序算法很难直接用到链表上。但是这里有个算法天然的可以用在链表上，就是归并排序算法
归并算法的核心就是分割组和合并有序组。这个是可以用在链表上的。对两个有序链表的合并可以说比有序数组的合并还简单。而对链表的分割也有好办法。
链表的分割用到了链表的常用算法：快慢指针法 先看链表定义：
typedef struct _Node{
int data;
struct _Node *next;
}Node, *PNode;
再看链表分割法，我们分割肯定也是按照中间分割，那么关键点就是找到中间链表节点
#include <stdlib.h>
#include <stdio.h>
#include "CNode.h"
PNode _getMiddleNode(PNode head) {
if (head == NULL || head->next == NULL) return head;
Node *fast = head->next, *slow = head;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
}
return slow;
}
这个方法里的快指针的速度是慢指针的两倍，所有快指针到达终点的时候，慢指针刚好走了一半。这里需要注意的数快指针的初始位置是比慢指针多一步的。然后按照中间分割点的话，慢指针是算在前一半里面的。
再看一下我们是如何用这个方法将链表进行分割的。
void sortSingleList(Node **head) {
if (head == NULL || (*head) == NULL || (*head)->next == NULL) return;
Node *midNode = _getMiddleNode(*head);
Node *restNode = midNode->next;
midNode->next = NULL;
sortSingleList(head);
sortSingleList(&restNode);
*head = _mergeSortedList(*head, restNode);
}
这里可以看到，分割方法和数组的递归分割法是一样的，都是递归调用，只不过这里多了一步计算链表中间节点的步骤。
再来看核心算法归并算法：
PNode _mergeSortedList(PNode head1, PNode head2) {
if (head1 == NULL) return head2;
if (head2 == NULL) return head1;
Node *newHead = NULL;
Node *p1 = head1;
Node *p2 = head2;
if (head1->data > head2->data) {
newHead = head2;
p2 = head2->next;
} else {
newHead = head1;
p1 = head1->next;
}
Node *cur = newHead;
while (p1 != NULL && p2 != NULL) {
if (p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
if (p1 != NULL) cur->next = p1;
if (p2 != NULL) cur->next = p2;
return newHead;
}
这里我采用的是非递归算法，要点是先把头节点确定，接下来的跟数组的合并算法差不多，注意最后元素合并跟数组不一样，只连接next节点，不需要while循环。 当然还有递归方式来实现_mergeSortedList方法，链表天生适合递归。这里就不说了，有兴趣的可以到我的github上看，那里有各种实现。
归并排序的其他应用
这里我只讲一种场景。就是外部排序。如果我们的要排序的数据量很大，而内存有比较小，我们该如何排序呢？这个也是经典面试题目。这里肯定是要用到归并排序，而且是多路归并排序，因为你需要将数据分为N份来拿到内存中排序，然后对着N份进行归并排序。这里面整体算法就复杂了，也不是这里可以说的明白的。有兴趣可以到网上查查资料。
好了，就到这。这篇文章历时两个月终于写完了。。。。有兴趣可以看 我写的各种算法github工程
如果你觉得这篇文章有用，请打赏小钱喝杯咖啡^_^
