merge Trong chỗ của hai mảng

Question

Chúng tôi có một loạt các kích thước m + n trong đó m yếu tố này là hiện tại, theo thứ tự sắp xếp, và một mảng thứ hai của kích thước n, một lần nữa theo thứ tự sắp xếp. Chúng tôi muốn cả hai được sắp xếp và hiển thị trong mảng đầu tiên. Không có mảng thứ ba là .

Ví dụ:

1, 3, 55, 66, 77, _, _, _ 
    5, 9, 20 

Câu trả lời sẽ là:

1, 3, 5, 9, 20, 55, 66, 77 

Answer 1

Thực hiện sắp xếp hợp nhất thông thường nhưng ngược lại so sánh các số lớn nhất trước tiên, lưu trữ (đảo ngược) vào cuối mảng đầu tiên quay ngược lại. Bằng cách này, các yếu tố bạn đang hợp nhất không bao giờ bị ghi đè (điều này hoạt động rất dễ dàng để xem nếu bạn nghĩ về nó một lúc).

Answer 2

Di chuyển các nội dung của mảng đầu đến cuối của mảng đầu tiên, chẳng hạn rằng các yếu tố có sản phẩm nào hiện nay có ngay từ đầu . Sau đó hợp nhất hai chuỗi như bình thường vào mảng đầu tiên.

Answer 3

Tại chỗ về cơ bản yêu cầu chúng tôi chỉ sử dụng bộ nhớ "liên tục", không thay đổi với các kích thước mảng đầu vào khác nhau. Tuy nhiên, câu hỏi tự phân bổ số lượng bộ nhớ bổ sung bằng với kích thước của một trong hai mảng đầu vào, đó là bộ nhớ O (n) trong trường hợp xấu nhất. Này về cơ bản làm cho ý tưởng "tại chỗ" vô nghĩa ...

Câu hỏi đặt ra có thể được phrased tốt hơn là "hợp nhất mà không cần thêm bộ nhớ", mà là một mô tả chính xác hơn về ý định thực sự của nó ...

Answer 4

// merge the elements in B[] to A[], starting from the last one 
    void merge(int A[], int m, int B[], int n) { 
     // m-1 and n-1 represent the current element index in A[] and B[] respectively 
     while (n > 0) { // there are still elements in B[] not merged 
      if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[] 
      A[m+n-1] = A[m-1]; // move current element of A[] to its right position 
      --m; // decrease current element index of A[] 
      } 
     else { // current element in A[] <= current element in B[] 
      A[m+n-1] = B[n-1]; // move current element in B[] to its right position 
      --n; // decrease current element index of B[] 
     } 
     } 
    }