归并排序算法（Java实现）

归并排序的基本思想是，将两个或两个以上元素的有序序列组合，使其成为一个有序序列。其中最为常用的是 2 路归并排序。

2 路归并排序的主要思想是，假设元素的个数是 n，将每个元素作为一个有序的子序列：

将相邻的子序列两两合并，得到 ⌊n/2⌋ 个长度为 2 的有序子序列；
继续将相邻的有序子序列两两合并，得到 ⌊n/4⌋ 个长度为 4 的有序子序列。

以此类推，重复执行以上操作，直到有序序列合并为一个为止。这样就得到了一个有序序列。

一组元素序列的关键字序列为 (37,19,43,22,57,89,26,92)，2 路归并排序过程如下图所示：

图 1 2路归并排序过程

可以看出，2 路归并排序其实就是不断地将两个相邻的子序列合并为一个子序列的过程。其合并算法如下：

public void Merge(int s[], int t[], int low, int mid, int high)
// 将有序的 s[low···mid] 和 s[mid + 1···high] 归并为有序的 t[low···high]
{
    int i = low;
    int j = mid + 1;
    int k = low;
    while(i <= mid && j <= high) // 将 s 中的元素由小到大地合并到 t
    {
        if (s[i] <= s[j])
        {
            t[k] = s[i];
            i++;
        }
        else {
            t[k] = s[j];
            j++;
        }
        k++;
    }
    while(i <= mid) // 将剩余的 s[i···mid] 复制到 t
    {
        t[k] = s[i];
        k++;
        i++;
    }
    while(j <= high) // 将剩余的 s[j···high] 复制到 t
    {
        t[k] = s[j];
        k++;
        j++;
    }
}

以上是合并两个子表的算法，可通过递归调用以上算法合并所有子表，从而实现 2 路归并排序。2 路归并排序算法描述如下：

public void TwoWayMergeSort(int s[], int t[], int low, int high)
// 使用 2 路归并排序将 s[low...high] 归并排序并存储到 t[low...high] 中
{
    int t2[] = new int[s.length];
    if (low == high)
        t[low] = s[low];
    else {
        int mid = (low + high) / 2;  // 将 s[low...high] 分为 s[low...mid] 和 s[mid+1...high]
        TwoWayMergeSort(s, t2, low, mid);  // 将 s[low...mid] 归并为有序的 t2[low...mid]
        TwoWayMergeSort(s, t2, mid + 1, high);  // 将 s[mid + 1...high] 归并为有序的 t2[mid + 1...high]
        Merge(t2, t, low, mid, high);  // 将 t2[low...mid] 和 t2[mid + 1...high] 归并到 t[low...high]
    }
}

归并排序的空间复杂度为 O(n)。由于 2 路归并排序所使用的空间过大，因此它主要用于外部排序。

2 路归并排序算法的时间复杂度为 O(nlogn)。2 路归并排序还是一种稳定的排序算法。

归并排序算法（Java实现）

相关文章