阿里笔试之非递归实现归并排序

原理放在开头：

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；

以上来自百度百科。

了解算法之前我们需要理解三个标记量，low低位、mid中间位、high高位。
以第二次归并为例：
归并前{6,202,100,301},{8,38,1}
前一组集合low=0,mid=1,high=3
而这次归并需要做的就是讲mid+1与mid+2插入{6,202}中。

看懂了原理下面来看如何实现

        /**
         * 
         * @param expresses 需要排序的集合
         * @param low 地位
         * @param mid 中间位
         * @param high 高位
         */
        public static void sort(LinkedList<Express> expresses,int low,int mid,int high){
            int i=low,j=mid+1;
            while (i<=high&&j<=high){
                if(expresses.get(i).time<=expresses.get(j).time){
                   //进行插入操作
                    Express express = expresses.get(j);
                    expresses.remove(j);
                    expresses.add(i,express);
                    j++;
                    if(j>high)
                        return;
                }
                i++;
            }
        }
        /**
         * 对LinkList进行排序
         * @param expresses
         */
        public static void mergeSort(LinkedList<Express> expresses){
            int size=1,low,mid,high;
            while (size<expresses.size()){
                low = 0;
                while (low+size<expresses.size()){
                    mid = low+size-1;
                    high = mid+size;
                    if(high>=expresses.size())
                        high = expresses.size()-1;
                    sort(expresses,low,mid,high);
                    low = high+1;
                }
                size*=2;
            }
        }

其实这样做算法的性能不太好，虽然LinkedList对插入删除比较方便，但是读取元素消耗比较大，建议利用链表实现。