谈谈归并排序算法

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工程

如果你觉得这篇文章有用，请打赏小钱喝杯咖啡^_^

Category: 算法 Tagged: 算法归并排序

2018-08-06