MergeSort-蒲公英云

MergeSort

向右看齐 2022-06-02 04:18 196阅读 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]前面。则这个排序算法是稳定的！

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]);
    }
}