归并排序(Merge sort)

很多的算法都是递归的结构,递归的目的呢,是在自己调用自己的时候,将问题分解成更小的问题,这个过程也叫做divide-and-conquer,通过把原来的问题的一个大问题,分解成一个更小的问题,再把更小的问题分解成微不足道的问题,再一一解决所有所有的问题。
devide-and-conquer一般是这样来解决问题的:
Divide:将问题分解成更小的,但是相似的问题
Conquer:递归解决这些小问题,如果小问题已经足够小,直接解决;否则可以重复Divide的过程
Combine:将解决小问题的方案合并和大的解决方案中,从而解决更大的问题
今天要说的归并排序,就是这样的一种模式。

归并排序算法

Divide:将n个要排序的元素分成两半,各占n/2
Conquer:用归并排序分别对两个n/2的元素排序
Combine:将两个排序的结果合并(Merge),产出最终结果
这是一个递归的过程,那递归到什么时候是个头呢?
当被分割的序列长度是1了,就该结束了,一个元素就不用排序了吧。
设想一个我们有
MERGE(A, p, q, r)
A就是我们要排序的序列
p,q,r都是A的index,满足条件p\<=q\<r,我们假设A[p..q]和A[q+1..r]是已经排序排好的,是有序的数组,于是我们总共有n个元素需要排序n = r – p + 1。
还是用打牌的观点来说,假如我们现在把一副牌洗乱,然后分成两堆,左右各一半。然后分别将左右两堆按从小到大排序,牌面均向上。
现在,我们想把这两堆牌合并在一起,并且是有序叠放的。就可以这样做:
* 比较左边和右边的牌,取小的那一张,拿出来,扣在桌子上。
* 再次比较两堆牌,取较小的一张,拿出来,扣在桌子上
* 重复上面的动作,直到所有的牌都合并在一起。
这就是归并排序。
可是这里面有个小问题,但某些情况下,可以左边已经没有牌了,右边还有一堆。这时候去比较左右两边的时候,是不是要先检查一下是否还有牌呢?
举个例子,左边的牌是
1,3,4,5
右边的牌是
2,6,7,8
我们来做归并排序:
1. 比较左右两堆,取出最小的1,扣在桌上
2. 比较左右两堆,取出最小的2,扣在桌上
3. 比较左右两堆,取出最小的3,扣在桌上
4. 比较左右两堆,取出最小的4,扣在桌上
5. 比较左右两堆,取出最小的5,扣在桌上
现在呢,1,2,3,4,5都排好序了,左边牌堆没有牌了。右边还有3张。那比较左右两边的时候,左边不就是null了?
这个时候呢,可以考虑弄个正无穷∞出来,两个牌堆是
1,3,4,5,∞和2,6,7,8,∞那就不用判断了。
根据这个思想,得出我们的伪代码。

伪代码

Merge(left, right)
    let result[1..left.length+right.length] be new arrays
    n = 0
    m = 0
    while n < left.length and m < right.length
        if left[n] <= right [m]
            result.add(left[n])
            n = n + 1
        else
            result.add(right[m])
            m = m + 1
    result.add(left[n..left.length])//如果还有剩下,加入左边剩余的部分
    result.add(right[m..right.length])//如果右边还有剩下,加入右边部分
return result

但是,怎么体现递归呢?
这儿还得有一段

Merge-Sort(seq, p, r)
    if seq.length <=1
        return seq
    middle = seq.length / 2
    left = Merge-Sort(seq[1..middle])
    right = Merge-Sort(seq[middle..seq.length])
    return Merge-Sort(left, right)

Python实现

def merge(left, right):
    result = []
    n, m = 0, 0
    while n < len(left) and m < len(right):
        if left[n] <= right[m]:
            result.append(left[n])
            n += 1
        else:
            result.append(right[m])
            m += 1

    result += left[n:]
    result += right[m:]
    return result

def sort(seq):
    if len(seq) <= 1:
        return seq

    middle = int(len(seq) / 2)
    left = sort(seq[:middle])
    right = sort(seq[middle:])
    return merge(left, right)

源码:Github-Syler-Fun-Merge-Sort-Python

Java实现

        public static void sort(int[] seq, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            sort(seq, left, middle);
            sort(seq, middle + 1, right);
            merge(seq, left, right);
        }
    }

    public static void merge(int[] seq, int l, int r) {
        int mid = (l + r) / 2;
        int i = l;
        int j = mid + 1;
        int count = 0;
        int temp[] = new int[r - l + 1];
        while (i <= mid && j <= r) {
            if (seq[i] < seq[j]) {
                temp[count++] = seq[i++];
            } else {
                temp[count++] = seq[j++];
            }
        }
        while (i <= mid) {
            temp[count++] = seq[i++];
        }
        while (j <= r) {
            temp[count++] = seq[j++];
        }
        count = 0;
        while (l <= r) {
            seq[l++] = temp[count++];
        }
    }

源码:Github-Syler-Fun-Merge-Sort-Java

发表评论

电子邮件地址不会被公开。 必填项已用*标注