算法笔记（第一部分）-- 排序之白话归并排序

归并排序是一种基于比较的排序算法，在多数的实现方法下它是稳定的。归并排序可是由计算机祖师级人物－冯 诺依曼提出的哦。

归并排序的过程：
1. 如果数据链表的长度为0或1，则返回
2. 将原始数据链表对半分成两个子链表
3. 对每个子链表递归的调用合并排序进行排序
4. 合并两个子链表使其成为一个排序完成的链表

归并排序的时间复杂度为О(nlogn)，空间复杂度为О(n)。

归并排序的动画：


归并排序代码－mergesort：

public int[] mergeSort(int[] data){
        if(data.length<=1)
              return data;
        int middle = data.length/2;
        int[] left = new int[middle];
        int[] right = new int[data.length-middle];
        for(int i=0; i<left.length; i++){
              left[i] = data[i];
        }
        for(int i=0; i<right.length;i++){ 
        	right[i] = data[middle+i];
        }
        left = mergeSort(left);
        right = mergeSort(right);
        int[] result = merge(left, right);
        return result;
    }
public int[] merge(int[] left,int[] right){
        int result[] = new int[left.length + right.length];
        int index = 0;//index of result
        int x = 0;//index of left
        int y = 0;//index of right 

        //compare each element in two arrays, after comparing, index++.
        while(x<left.length && y<right.length){
              if(left[x]<right[y]){
                    result[index++] = left[x++];
              }else{
                    result[index++] = right[y++];
              }
        }
       
        //the length of two arrays might be different, 
        //so we have to copy the rest elements in two arrays
        while(x<left.length)  
              result[index++] = left[x++];  
        while(y<right.length)  
              result[index++] = right[y++];
        return result;
  }

归并排序的示意图：


由以上示意图可以看出mergesort的过程很简单，白话一点就是：拆分拆分拆分直至每个链表中仅有一个元素，合并合并合并至最终排好序的链表。merge是核心，经过递归调用归并排序后产生的left与right是已经排好序的两个子链表，依次比较left与right中的两数，将其放入适当的位置，然后删除子链表中已经放入result的那个数，最后将left与right中剩余的数依次放入result。问题：在实现的算法中，每次都要产生很多临时的list，这样效率是不是不高？

另曾经去一家小公司面试，工程师出了一道题：给定两个排好序的数组，如何将其合并是新的数组依然有序，似乎就是归并排序的应用，我的答案：

public int[] merge(int[] left,int[] right){
            int result[] = new int[left.length + right.length];
            int index = 0;//index of result
            int x = 0;//index of left
            int y = 0;//index of right 

            //compare each element in two arrays, after comparing, index++.
            while(x<left.length && y<right.length){
                  if(left[x]<right[y]){
                        result[index++] = left[x++];
                  }else{
                        result[index++] = right[y++];
                  }
            }
           
            //the length of two arrays might be different, 
            //so we have to copy the rest elements in two arrays
            while(x<left.length)  
                  result[index++] = left[x++];  
            while(y<right.length)  
                  result[index++] = right[y++];
            return result;
      }

代码的思想：将两个数组中的每一个数经过比较填入结果数组，由于可能两个数组的长度不等，最后还要将那个数组中剩余的数填入结果数组。

评论

3 楼 cy729215495 2008-10-08  

我仔细的把你的算法研究了一遍，发现有点问题，本来算法是要求把一个数组最后分成零散的一个一个的，你的二次递归方法完全是没有必要的，更重要的是left和right并不是紧挨的两个元素在归并，不如直接取这个data里面的两个紧挨着的元素比较，不需要递归。欢迎和我探讨 ，我qq：729215495

2 楼 litianyi520 2008-09-08  

package java.util.Arrays;
里面的sort方法 好像也是冒泡排序，

private static void sort1(int x[], int off, int len) {
// Insertion sort on smallest arrays
if (len < 7) {
    for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
    swap(x, j, j-1);
    return;
}

swap 方法 和c的写法一样
   private static void swap(long x[], int a, int b) {
long t = x[a];
x[a] = x[b];
x[b] = t;
    }

1 楼 farryu 2008-09-03  

lz的算法一看就知道是原创的，呵呵，很值得佩服，不过建议lz可以看看collection包中Arrays的sort的归并排序，可用性比较高