MergeSort

向右看齐 2022-06-02 04:18 109阅读 0赞

从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：  
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;   
② 求解 -- 递归地对两个子区间a\[low...mid\] 和 a\[mid+1...high\]进行归并排序。递归的终结条件是子区间长度为1。  
③ 合并 -- 将已排序的两个子区间a\[low...mid\]和 a\[mid+1...high\]归并为一个有序的区间a\[low...high\]。

归并排序时间复杂度  
归并排序的时间复杂度是O(N\*lgN)。  
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？  
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(N\*lgN)。  
  
归并排序稳定性  
归并排序是稳定的算法，它满足稳定算法的定义。  
算法稳定性 -- 假设在数列中存在a\[i\]=a\[j\]，若在排序之前，a\[i\]在a\[j\]前面；并且排序之后，a\[i\]仍然在a\[j\]前面。则这个排序算法是稳定的！

![151853346211212.jpg][]

package sort;
    
    import java.util.ArrayList;
    
    /**
     * UpToDown
     * Created by long.chen  on 2018/1/3.
     */
    public class MergeSort<T extends Comparable<T>> {
        /**
         * @param array
         * @param start
         * @param middle
         * @param end
         */
        public void mergn(T[] array, int start, int middle, int end) {
    
            ArrayList<T> arrayList = new ArrayList<>(end - start + 1);//存放合并数据
            int i = start;//第一个区域的索引
            int j = middle + 1;//第二个区域的索引
            int k = 0;//arrayList 的区域索引
            while (i <= middle && j <= end) {
                if (array[i].compareTo(array[j]) < 0)
                    arrayList.add(k++, array[i++]);
                else
                    arrayList.add(k++, array[j++]);
            }
            while (i <= middle)
                arrayList.add(k++, array[i++]);
            while (j <= end)
                arrayList.add(k++, array[j++]);
            for (i = 0; i < k; i++)
                array[start + i] = arrayList.get(i);
            arrayList = null;
        }
    
        public void mergeSortUptoDown(T[] array, int start, int end) {
            if (start == end || array == null)
                return;
            int middle = (start + end) / 2;
            mergeSortUptoDown(array, start, middle);
            mergeSortUptoDown(array, middle + 1, end);
            mergn(array, start, middle, end);
        }
    
        public static void main(String[] args) {
            MergeSort<Integer> mergeSort = new MergeSort<>();
            Integer data[] = {1, 45, 5, 96, 26, 31, 5, 0, 5, 5};
            mergeSort.mergeSortUptoDown(data, 0, data.length - 1);
            for (int i = 0; i < data.length; i++)
                System.out.printf("%d ", data[i]);
        }
    }

[151853346211212.jpg]: /images/20220602/8dc79764ec144f89bf479c8367d6a3c7.png