排序算法总结之归并排序

一,归并排序介绍

归并排序是一个典型的基于分治的递归算法。它不断地将原数组分成大小相等的两个子数组(可能相差1),最终当划分的子数组大小为1时(下面代码第17行left小于right不成立时) ,将划分的有序子数组合并成一个更大的有序数组。为什么是有序子数组???

归并排序的递归公式:T(N) = 2T(N/2) + O(N)

从公式中可以看出:将规模为 N 的原问题分解成两个规模 N/2 的两个子问题;并且,合并这两个子问题的代价是 O(N)---[后面的 +O(N) 表示合并的代价] 

二,归并排序算法分析

归并排序算法有两个基本的操作,一个是分,也就是把原数组划分成两个子数组的过程。另一个是治,它将两个有序数组合并成一个更大的有序数组。

它将数组平均分成两部分: center = (left + right)/2,当数组分得足够小时---数组中只有一个元素时,只有一个元素的数组自然而然地就可以视为是有序的,此时就可以进行合并操作了。因此,上面讲的合并两个有序的子数组,是从 只有一个元素 的两个子数组开始合并的。

合并后的元素个数:从 1-->2-->4-->8......

比如初始数组:[24,13,26,1,2,27,38,15]

①分成了两个大小相等的子数组:[24,13,26,1]    [2,27,38,15]

②再划分成了四个大小相等的子数组:[24,13]  [26,1]    [2,27]   [38,15]

③此时,left < right 还是成立,再分:[24]  [13]  [26]    [1]    [2]    [27]   [38]  [15]

此时,有8个小数组,每个数组都可以视为有序的数组了!!!,每个数组中的left == right,从递归中返回(从19行--20行的代码中返回),故开始执行合并(第21行):

merge([24],[13]) 得到 [13,24]

merge([26],[1]) 得到[1,26]

.....

.....

最终得到 有序数组。

三,归并排序算法实现

public class MergeSort {

public static <T extends Comparable<? super T>> void mergeSort(T[] arr) {
        T[] tmpArray = (T[]) new Comparable[arr.length];
        mergeSort(arr, tmpArray, 0, arr.length - 1);
    }

/**
    *
    * @param arr an array of Comparable items
    * @param tmpArray an array to place the merge result
    * @param left the left-most index of the array
    * @param right right-most index of the array
    */
    private static <T extends Comparable<? super T>> void mergeSort(T[] arr,
            T[] tmpArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(arr, tmpArray, left, center);
            mergeSort(arr, tmpArray, center + 1, right);
            merge(arr, tmpArray, left, center + 1, right);
        }
    }

/**
    *
    * @param arr an array of Comparable items
    * @param tmpArray an array to place the merge result
    * @param leftPos the left-most index of the subarray
    * @param rightPos the index of the start of the second half
    * @param rightEnd the right-most index of the subarray
    */
    private static <T extends Comparable<? super T>> void merge(T[] arr,
            T[] tmpArray, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int numElements = rightEnd - leftPos + 1;
        int tmpPos = leftPos;// 只使用tmpArray中某一部分区域
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (arr[leftPos].compareTo(arr[rightPos]) <= 0)
                tmpArray[tmpPos++] = arr[leftPos++];
            else
                tmpArray[tmpPos++] = arr[rightPos++];
        }

while (leftPos <= leftEnd)
            tmpArray[tmpPos++] = arr[leftPos++];// copy rest of left half
        while (rightPos <= rightEnd)
            tmpArray[tmpPos++] = arr[rightPos++];// copy rest of right half

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/fcb619f73f3181dbb315d7e780aa06ee.html