将两个非顺序数组升序排序为一个数组

Question

在处理序号之后，我试图将两个具有非序号的数组排序为一个数组。我需要单独订购阵列还是有更有效的方法？

如果我运行我输出下面的代码将是 4,16,2,11,19.. 它应该是 0,1,2,3,4..

    int myFirstArray [] = { 16, 2, 11, 34, 77, 1, 0, 10, 3 };
    int mySecondArray [] = { 4, 19, 6, 32, 8, 10, 66 };
    int firstPos = 0, secondPos = 0;

    int myThirdArray [] = new int[myFirstArray.length + mySecondArray.length];

    for (int i = 0; i < myThirdArray.length; i++) {
        if (firstPos < myFirstArray.length && secondPos < mySecondArray.length) {
            if (mySecondArray[secondPos] < myFirstArray[firstPos]) {
                myThirdArray[i] = mySecondArray[secondPos];
                secondPos++;
            }
            else {
                myThirdArray[i] = myFirstArray[firstPos];
                firstPos++;
            }       
        }
        else if (secondPos < mySecondArray.length) {
            myThirdArray[i] = mySecondArray[secondPos];
            secondPos++;
        }
        else {
            myThirdArray[i] = myFirstArray[firstPos];
            firstPos++;
        }
    }

    for(int i = 0; i < myThirdArray.length; i++) {
        System.out.println(myThirdArray[i]);
    }

Answer 1

如果您有 2 个排序数组并想将它们组合成一个排序数组，那么您的代码就是正确的。但是您正在比较未排序数组的前 2 个元素并创建一个局部排序数组，这意味着数组的某些元素与其他元素相比已排序，即 4 < 16、2 < 11 < 19.

你的逻辑与Mergesort. You split your array into halves and split them again and merges the 2 halves. You end up merging arrays of size 1, then merging arrays of size 2 and so on and so on. Your merging code is correct. You can see more details here相去不远。

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[l + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[m + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
    if (l < r)
    {
        // Find the middle point
        int m = (l+r)/2;

        // Sort first and second halves
        sort(arr, l, m);
        sort(arr , m+1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

Answer 2

最好先对两个数组进行排序，然后将两个数组合并为一个数组。

// Function to merge array in sorted order
// a[] will be the first unsorted array.
// b[] will be the second unsorted array.
public static int[] sortedMerge(int a[], int b[]){

    int n = a.length;
    int m = b.length;
    int totalSize=n+m;

    //result array
    int[] res =new int[totalSize];

    // Sorting a[] and b[]
    Arrays.sort(a);
    Arrays.sort(b);

    // Merge two sorted arrays into res[]
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) {
            res[k] = a[i];
            i += 1;
            k += 1;
        } else {
            res[k] = b[j];
            j += 1;
            k += 1;
        }
    }    

    while (i < n) {  // Merging remaining
                     // elements of a[] (if any)
        res[k] = a[i];
        i += 1;
        k += 1;
    }    
    while (j < m) {   // Merging remaining
                     // elements of b[] (if any)
        res[k] = b[j];
        j += 1;
        k += 1;
    }
 return res;
}

这样时间复杂度将为 O(nlogn + mlogm + (n + m)) 并且 Space 复杂度为 O ( (n + m) )。如果你想先合并数组，然后对合并后的数组进行排序，那么 space 复杂度将是相同的，但时间复杂度将变为 O((n + m)(log(n + m)))，这肯定会比第一个高。

Answer 3

创建一个新的 array3，大小总和为 array1.length 和 array2.length
使用 System.arrayCopy() 将 array1 复制到 array3 从索引 0
使用 System.arrayCopy() 将 array2 复制到 array3 从索引 array1.length
按您喜欢的方式对 array3 进行排序，例如Arrays.sort() 或任何 other algorithm

将两个非顺序数组升序排序为一个数组

Sorting two non-sequential arrays to one array ascending

java

arrays

sorting

nonsequential