0

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

如果我运行下面的代码，我的输出将是 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]);
    }
4

3 回答 3

0

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

// 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))，空间复杂度为 O ( (n + m) )。如果你想先合并数组，然后对合并后的数组进行排序，那么空间复杂度会一样，但时间复杂度会变成O((n + m)(log(n + m)))，肯定会更高比第一个。

于 2017-09-13T19:00:59.347 回答
0
  1. 创建一个新array3的大小总和为array1.lengthandarray2.length
  2. 用于System.arrayCopy()复制array1到array3从索引开始0
  3. 用于System.arrayCopy()复制array2到array3从索引开始array1.length
  4. array3以您喜欢的方式排序，例如Arrays.sort()或任何other algorithm
于 2017-09-13T19:56:57.540 回答
0

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

您的逻辑离Mergesort不远。您将数组分成两半并再次拆分它们并合并两半。您最终会合并大小为 1 的数组，然后合并大小为 2 的数组，依此类推。您的合并代码是正确的。您可以 在此处查看更多详细信息。

// 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);
    }
}
于 2017-09-13T18:44:17.670 回答