合并排序最有效的实现 [英] Merge Sort most efficient implementation

问题描述

因此，我想知道Java中最有效的合并排序实现是(如果时间上的效率可能会因语言而异).这个问题可能微不足道，但是我的最终目标是向经验丰富的程序员学习.这是我制作的2个示例:

So I wonder what is the most efficient implementation of a merge sort in Java (In case its efficiency in terms of time can change depending on the language). This question may be trivial but my ultimate goal is to learn from more experienced programmers. Here are 2 examples I made:

//version I made.
public static double[] mergeSort(double[] arreglo) {
    if (arreglo.length > 1) {
        int d = (arreglo.length / 2);
        double[] arreglo1 = Arrays.copyOfRange(arreglo, 0, d),
                arreglo2 = Arrays.copyOfRange(arreglo, d, arreglo.length);
        arreglo1 = mergeSort(arreglo1);
        arreglo2 = mergeSort(arreglo2);
        return merge(arreglo1, arreglo2);
    } else {
        return arreglo;
    }
}

public static double[] merge(double[] arreglo1, double[] arreglo2) {
    double[] convi = new double[arreglo1.length + arreglo2.length];
    for (int i = 0, m1 = 0, m2 = 0; i < convi.length; i++) {
        if (arreglo1.length > m1 && arreglo2.length > m2) {
            if (arreglo1[m1] <= arreglo2[m2])
                convi[i] = arreglo1[m1++];
            else {
                convi[i] = arreglo2[m2++];
            }
        } else {
            convi[i] = (arreglo1.length == m1) ? arreglo2[m2++] : arreglo1[m1++];
        }
    }
    return convi;
}

//Taken out of Cormens book.
public static void mergeSort(int[] arreglo, int i, int f) {
    if (f > i) {
        int d = ((i + f) / 2);
        mergeSort(arreglo, i, d);
        mergeSort(arreglo, d + 1, f);
        merge(arreglo, i, d, f);
    }
}


public static void merge(int[] arreglo, int i, int m, int f) {
    int n1 = (m - i) + 1;
    int n2 = (f - m);
    int[] mitad1 = new int[n1 + 1];
    int[] mitad2 = new int[n2 + 1];
    for (int v = 0; v < n1; v++) {
        mitad1[v] = arreglo[i + v];
    }
    for (int p = 0; p < n2; p++) {
        mitad2[p] = arreglo[p + m + 1];
    }
    mitad1[n1] = Integer.MAX_VALUE;
    mitad2[n2] = Integer.MAX_VALUE;
    for (int r = i, m1 = 0, m2 = 0; r <= f; r++) {
        if (mitad1[m1] <= mitad2[m2]) {
            arreglo[r] = mitad1[m1];
            m1++;
        } else {
            arreglo[r] = mitad2[m2];
            m2++;
        }
    }
}

推荐答案

以下程序是从 C ++中的Robert Sedgewick算法，第1-4部分

它介绍了一种改进.它将整个排序数组的一个副本复制到一个辅助数组中，该辅助数组将进一步处理.接下来，通过在辅助数组和原始数组之间进行交替来对辅助数组进行递归拆分，以使合并后的数组不会发生额外的复制操作.基本上，该算法在每个递归调用中切换输入数组和辅助数组的角色.例如，从概念上讲:

It introduces one type of improvement. It does a single copy of the whole sorting array into a an auxiliary array that is further dealt with. Next, the recursion splitting is done on the auxiliary array by alternating between the auxiliary array and original array so that the extra copying operation of the merged arrays doesn’t happen. Basically, the algorithm switches the role of the input and auxiliary array in each recursive call. For example, conceptually:

常规合并排序:

-合并

(((8) (5))((2) (3)))(((1) (7))((4) (6)))

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

-- copy back and ignore previous (UNNECESSARY)

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

– – – – – – – –

– – – – – – – –

该程序:

-合并

(((8) (5))((2) (3)))(((1) (7))((4) (6)))

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))

-向后合并

( 2 3 5 8 )( 1 4 6 7 )

(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))    

此外，在将数组分为两半后，该数组就足够小了，该算法使用插入排序，因为它在小型数据集上的表现要好于 merge sort .准确确定何时使用插入排序的阈值可以通过反复试验确定.

Also, after splitting the array into halves gives small enough arrays, the algorithm uses insertion sort since it performs better on small data sets than merge sort. The threshold for when exactly to use insertion sort can be determined with trial-and-error.

代码:

static int M = 10;

//insertion sort to be used once the mergesort partitions become small enough
static void insertionsort(int[] a, int l, int r) {
    int i, j, temp;
    for (i = 1; i < r + 1; i++) {
        temp = a[i];
        j = i;
        while ((j > 0) && a[j - 1] > temp) 
        {
            a[j] = a[j - 1];
            j = j - 1;
        }
        a[j] = temp;
    }
}

//standard merging two sorted half arrays into single sorted array
static void merge(int[] merged_a, int start_a, int[] half_a1, int start_a1, int size_a1, 
                         int[] half_a2, int start_a2, int size_a2) {
    int i, j, k;
    int total_s = size_a1 + size_a2;
    for (i = start_a1, j = start_a2, k = start_a; k < (total_s); k++) {
        // if reached end of first half array, run through the loop 
        // filling in only from the second half array
        if (i == size_a1) {
            merged_a[k] = half_a2[j++];
            continue;
        }
        // if reached end of second half array, run through the loop 
        // filling in only from the first half array
        if (j == size_a2) {
            merged_a[k] = half_a1[i++];
            continue;
        }
        // merged array is filled with the smaller element of the two 
        // arrays, in order
        merged_a[k] = half_a1[i] < half_a2[j] ?
                      half_a1[i++] : half_a2[j++];
    }
}

//merge sort data during merging without the additional copying back to array
//all data movement is done during the course of the merges
static void mergesortNoCopy(int[] a, int[] b, int l, int r) {
    if (r - l <= M) {
        insertionsort(a + l, l, r - l);
        return;
    }
    int m = (l + r) / 2;
    //switch arrays to msort b thus recursively writing results to b
    mergesortNoCopy(b, a, l, m); //merge sort left
    mergesortNoCopy(b, a, m + 1, r); //merge sort right
    //merge partitions of b into a
    merge(a, l, b, l, m - l + 1, b, m + 1, r - m); //merge
}

static void mergesort(int[] a) {
    int[] aux = Arrays.copyOf(a, a.length);
    mergesortNoCopy(a, aux, 0, a.length - 1);
}

其他一些可能的改进:

如果已排序则停止.

检查上半部最大的项目是否小于下半部的最小项目.帮助部分排序的数组.

Check if the largest item in first half ≤ smallest item in second half. Helps for partially-ordered arrays.

// after split, before merge
if (a[mid] <= a[mid + 1]) return;

编辑:这是一个好的文档我发现了Mergesort的不同版本及其改进.

here is a good document I found on different versions of Mergesort and improvements thereof.

这篇关于合并排序最有效的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！