归并排序 Java

Merge Sort Java

提问by Sam

I am trying to make a merge sort method, but it keeps on giving the wrong sorts. Where do I have change to make it actually sort the array? What part of the code has to be different? Thank you for your time.

我正在尝试创建一个合并排序方法，但它一直在给出错误的排序。我在哪里可以更改以使其实际对数组进行排序？代码的哪一部分必须不同？感谢您的时间。

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {  
        int elements = (rHigh - lHigh +1) ;  
        int[] temp = new int[elements];
        int num = left;
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= array[right]) {
          temp[num] = array[left];
          left++;
        }
        else {
          temp[num] = array[right];
          right++;
        }
       num++;   
      }
     while (left <= right){
        temp[num] = array[left]; // I'm getting an exception here, and is it because of the num???
        left += 1;
        num += 1;  
     }  
     while (right <= rHigh) {
        temp[num] = array[right];
        right += 1;
        num += 1;  
     }  
     for (int i=0; i < elements; i++){
       array[rHigh] = temp[rHigh];
       rHigh -= 1;   
     }

EDIT: now the mergeSort doesn't really sort the numbers, can someone tell me where it specifically is? especially when I print the "Testing merge sort" part.

编辑：现在合并排序并没有真正对数字进行排序，有人能告诉我它具体在哪里吗？特别是当我打印“测试合并排序”部分时。

采纳答案by Jeremy Powell

First of all, I'm assuming this is academic rather than practical, since you're not using a built in sort function. That being said, here's some help to get you moving in the right direction:

首先，我假设这是学术性的而不是实用的，因为您没有使用内置的排序功能。话虽如此，这里有一些帮助，可以让您朝着正确的方向前进：

Usually, one can think of a merge sort as two different methods: a merge() function that merges two sorted lists into one sorted list, and mergeSort() which recursively breaks the list into single element lists. Since a single element list is sorted already, you then merge all the lists together into one big sorted list.

通常，可以将合并排序视为两种不同的方法：merge() 函数将两个排序列表合并为一个排序列表，mergeSort() 将列表递归分解为单个元素列表。由于已经对单个元素列表进行了排序，因此您可以将所有列表合并到一个大的排序列表中。

Here's some off-hand pseudo-code:

这是一些现成的伪代码：

merge(A, B):
  C = empty list

  While A and B are not empty:
    If the first element of A is smaller than the first element of B:
      Remove first element of A.
      Add it to the end of C.
    Otherwise:
      Remove first element of B.
      Add it to the end of C.

  If A or B still contains elements, add them to the end of C.

mergeSort(A):
  if length of A is 1:
    return A

  Split A into two lists, L and R.

  Q = merge(mergeSort(L), mergeSort(R))

  return Q

Maybe that'll help clear up where you want to go.

也许这会有助于弄清楚你想去哪里。

If not, there's always MergeSortat wikipedia.

如果没有，维基百科上总会有MergeSort。

Additional:

附加：

To help you out, here are some comments inline in your code.

为了帮助您，这里有一些内嵌在您的代码中的注释。

  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // what do lHigh and rHigh represent?

        int elements = (rHigh - lHigh +1) ;     
        int[] temp = new int[elements];
        int num = left;

      // what does this while loop do **conceptually**? 
      while ((left <= lHigh) && (right <= rHigh)){
       if (a[left] <= a[right]) {
          // where is 'pos' declared or defined?
          temp[pos] = a[left];
          // where is leftLow declared or defined? Did you mean 'left' instead?
          leftLow ++;
        }
        else {
          temp[num] = a[right];
          right ++;
        }
       num++;   
      }

     // what does this while loop do **conceptually**?
     while (left <= right){
        // At this point, what is the value of 'num'?
        temp[num] = a[left];
        left += 1;
        num += 1;   
     }
     while (right <= rHigh) {
        temp[num] = a[right];
        right += 1;
        num += 1;       
     }
     // Maybe you meant a[i] = temp[i]?
     for (int i=0; i < elements; i++){
       // what happens if rHigh is less than elements at this point? Could
       // rHigh ever become negative? This would be a runtime error if it did
       a[rHigh] = temp[rHigh];
       rHigh -= 1;      
     }

I'm purposefully being vague so you think about the algorithm. Try inserting your own comments into the code. If you can write what is conceptually happening, then you may not need Stack Overflow :)

我故意含糊其辞，所以你考虑一下算法。尝试在代码中插入您自己的注释。如果您可以写出概念上发生的事情，那么您可能不需要 Stack Overflow :)

My thoughts here are that you are not implementing this correctly. This is because it looks like you're only touching the elements of the array only once (or close to only once). This means you have a worst case scenario of O(N)Sorting generally takes at least O(N * log N)and from what I know, the simpler versions of merge sort are actually O(N^2).

我的想法是你没有正确地实现这一点。这是因为看起来您只接触了数组的元素一次（或接近一次）。这意味着你有一个O(N)排序的最坏情况，通常至少需要，据O(N * log N)我所知，合并排序的更简单版本实际上是O(N^2).

More:

更多的：

In the most simplistic implementation of merge sort, I would expect to see some sort of recursionin the mergeSort() method. This is because merge sort is generally defined recursively. There are ways to do this iteratively using for and while loops, but I definitely don't recommend it as a learning tool until you get it recursively.

在合并排序的最简单实现中，我希望在 mergeSort() 方法中看到某种递归。这是因为归并排序通常是递归定义的。有很多方法可以使用 for 和 while 循环迭代地做到这一点，但我绝对不建议将其作为学习工具，直到您递归地获得它。

Honestly, I suggest taking either my pseudo-code or the pseudo-code you may find in a wikipedia article to implement this and start over with your code. If you do that and it doesn't work correctly still, post it here and we'll help you work out the kinks.

老实说，我建议使用我的伪代码或您在维基百科文章中可能找到的伪代码来实现这一点，然后重新开始使用您的代码。如果您这样做了，但仍然无法正常工作，请将其张贴在此处，我们将帮助您解决问题。

Cheers!

干杯!

And finally:

最后：

  // Precondition: array[left..lHigh] is sorted and array[right...rHigh] is sorted.
  // Postcondition: array[left..rHigh] contains the same elements of the above parts, sorted.
  public static void mergeSort(int[] array, int left,  int lHigh, int right, int rHigh) {   
        // temp[] needs to be as large as the number of elements you're sorting (not half!)
        //int elements = (rHigh - lHigh +1) ;
        int elements = rHigh - left;

        int[] temp = new int[elements];

        // this is your index into the temp array
        int num = left;

        // now you need to create indices into your two lists
        int iL = left;
        int iR = right;

        // Pseudo code... when you code this, make use of iR, iL, and num!
        while( temp is not full ) {
           if( left side is all used up ) {
             copy rest of right side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if ( right side is all used up) {
             copy rest of left side in.
             make sure that at the end of this temp is full so the
               while loop quits.
           }
           else if (array[iL] < array[iR]) { ... }
           else if (array[iL] >= array[iR]) { ... }
        }
 }

回答by Varun Verma

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};

        print(arr);
        new MergeSort().sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);           // recursive call to divide the sub-list
            sort(arr, mid + 1, hi);       // recursive call to divide the sub-list
            merge(arr, lo, mid, hi);      // merge the sorted sub-lists.
            print(arr);
        }
    }

    private void merge(int[] arr, int lo, int mid, int hi) {
        // allocate enough space so that the extra 'sentinel' value
        // can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
        // This function only merges them into a sorted list.
        int[] left = new int[(mid - lo) + 2];        
        int[] right = new int[hi - mid + 1];         


        // create the left and right sub-list for merging into original list.
        System.arraycopy(arr, lo, left, 0, left.length - 1);
        System.arraycopy(arr, mid + 1, right, 0, left.length - 1);

        // giving a sentinal value to marking the end of the sub-list.
        // Note: The list to be sorted is assumed to contain numbers less than 100.
        left[left.length - 1] = 100;
        right[right.length - 1] = 100;

        int i = 0;
        int j = 0;

        // loop to merge the sorted sequence from the 2 sub-lists(left and right) 
        // into the main list.
        for (; lo <= hi; lo++) {
            if (left[i] <= right[j]) {
                arr[lo] = left[i];
                i++;
            } else {
                arr[lo] = right[j];
                j++;
            }
        }
    }

    // print the array to console.
    private static void print(int[] arr) {
        System.out.println();
        for (int i : arr) {
            System.out.print(i + ", ");
        }
    }
}

回答by Sam Dozor

Here's another!

这是另一个！

private static int[] mergeSort(int[] input){
    if (input.length == 1)
        return input;

    int length = input.length/2;
    int[] left = new int[length];
    int[] right = new int[input.length - length];

    for (int i = 0; i < length; i++)
        left[i] = input[i];
    for (int i = length; i < input.length; i++)
        right[i-length] = input[i];

    return merge(mergeSort(left),mergeSort(right));
}

private static int[] merge(int[] left, int[] right){
    int[] merged = new int[left.length+right.length];
    int lengthLeft = left.length;
    int lengthRight = right.length;
    while (lengthLeft > 0 && lengthRight > 0){
        if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
            merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
            lengthLeft--;
        }else{
            merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
            lengthRight--;
        }
    }
    while (lengthLeft > 0){
        merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
        lengthLeft--;
    }
    while (lengthRight > 0){
        merged[merged.length - lengthRight] = right[right.length-lengthRight];
        lengthRight--;
    }
    return merged;
}

回答by Arun Dutta

static void mergeSort(int arr[],int p, int r) {

   if(p<r) {
        System.out.println("Pass "+k++);

        int q = (p+r)/2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        //System.out.println(p+" "+q+" "+r);
        merge(arr,p,q,r);
    }

}

static void merge(int arr[],int p,int q,int r) {
    int temp1[],temp2[];

    //lower limit array
    temp1 = new int[q-p+1];

    //upper limit array
    temp2 = new int[r-q];

    for(int i=0 ; i< (q-p+1); i++){
        temp1[i] = arr[p+i];
    }

    for(int j=0; j< (r-q); j++){
        temp2[j] = arr[q+j+1];
    }

    int i = 0,j=0;

    for(int k=p;k<=r;k++){

        // This logic eliminates the so called sentinel card logic mentioned in Coreman
        if(i!= temp1.length
                && (j==temp2.length || temp1[i] < temp2[j])
               ) {
            arr[k] = temp1[i];
           // System.out.println(temp1[i]);
            i++;
        }
        else {
            //System.out.println(temp2[j]);
            arr[k] = temp2[j];

            j++;
        }
    }
}

回答by Akashdeep Singh

>

>

Merge Sort Using Sentinel

使用 Sentinel 进行归并排序

This codes works perfectly fine.

这段代码工作得很好。

 public void mergeSort(int a[], int low, int high) {

   if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);

    }
}



public void merge(int a[], int low, int mid, int high) {
    int n1 = mid - low + 1;// length of an array a1
    int n2 = high - mid; // length of an array a2
    int a1[] = new int[n1 + 1];
    int a2[] = new int[n2 + 1];
    int lowRange = low;
    for (int i = 0; i < n1; i++) {
        a1[i] = a[lowRange];
        lowRange++;
    }
    for (int j = 0; j < n2; j++) {
        a2[j] = a[mid + j + 1];
    }
    a1[n1] = Integer.MAX_VALUE; // inserting sentinel at the end of array a1 
    a2[n2] = Integer.MAX_VALUE; // inserting sentinel at the end of array a2
    int i = 0;
    int j = 0;
    int k = low;
    for (k = low; k <= high; k++) {

            if (a1[i] >= a2[j]) {
                a[k] = a2[j];
                j++;
            } else {
                a[k] = a1[i];
                i++;
            }

    }
    if (a2.length >= a1.length) {
        for (int ab = k; ab < a2.length; ab++) {
            a[k] = a2[ab];
            k++;
        }
    } else if (a1.length >= a2.length) {
        for (int ab = k; ab < a1.length; ab++) {
            a[k] = a1[ab];
            k++;
        }
    }

}

回答by user3402754

Here's another alternative:

这是另一种选择：

public class MergeSort {
public static void merge(int[]a,int[] aux, int f, int m, int l) {

    for (int k = f; k <= l; k++) {
        aux[k] = a[k];
    }

    int i = f, j = m+1;
    for (int k = f; k <= l; k++) {
        if(i>m) a[k]=aux[j++];
        else if (j>l) a[k]=aux[i++];
        else if(aux[j] > aux[i]) a[k]=aux[j++];
        else a[k]=aux[i++];
    }       
}
public static void sort(int[]a,int[] aux, int f, int l) {
    if (l<=f) return;
    int m = f + (l-f)/2;
    sort(a, aux, f, m);
    sort(a, aux, m+1, l);
    merge(a, aux, f, m, l);
}
public static int[] sort(int[]a) {
    int[] aux = new int[a.length];
    sort(a, aux, 0, a.length-1);
    return a;
}

}

}

回答by Tushar Mahajan

package com;

包com;

public class Test {
    int count = 0;

    public static void main(String[] args) {
        int a[] = {1,3,5,7,9,10,14,15,16};
        int b[] = {2,4,6,8,11,12,13,17,18};

        int sizec = a.length+b.length;

        int c[] = new int[sizec];

        int i=0;int j=0;int k=0;

        while(k<sizec)
        {
             if(i == a.length || j == b.length)
                {
                 int sizeDifference = 0;
                 if(i==a.length)
                 {
                     sizeDifference = b.length-j;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = b[m+j];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }

                 else if(j== b.length)
                 {
                     sizeDifference = a.length-i;
                     for (int m =0;m<sizeDifference;m++)
                        {
                            c[k] = a[m+i];
                            if(k<sizec)
                            k++;
                        }
                        break;
                 }
                 else
                 {
                     c[k] = b[j];
                        j++;
                 }

                }

            if(i < a.length || j < b.length )
            {
            if(a[i]>b[j] )
                    {
                        c[k]=b[j];
                        j++;
                    }
            else if(a[i]<b[j])
            {
                c[k]=a[i];
                i++;
            }
            }



            k++;
        }

        for(int l=0;l<sizec;l++)
        {
            System.out.println(c[l]);
        }


    }
}

回答by kundus

Here is a simple merge sort algorithm in Java:

这是一个简单的 Java 合并排序算法：

Good Tip: Always use int middle = low + (high-low)/2instead of int middle = (low + high)/2.

好提示：始终使用int middle = low + (high-low)/2而不是int middle = (low + high)/2.

public static int[] mergesort(int[] arr) {
    int lowindex = 0;
    int highindex = arr.length-1;
    mergesort(arr, lowindex, highindex);
    return arr;
}

private static void mergesort(int[] arr, int low, int high) {
    if (low == high) {
        return;
    } else {
        int midIndex = low + (high-low)/2;
        mergesort(arr, low, midIndex);
        mergesort(arr, midIndex + 1, high);
        merge(arr, low, midIndex, high);
    }
}
private static void merge(int[] arr, int low, int mid, int high) {
    int[] left = new int[mid-low+2];
    for (int i = low; i <= mid; i++) {
        left[i-low] = arr[i];
    }
    left[mid-low+1] = Integer.MAX_VALUE;
    int[] right = new int[high-mid+1];
    for (int i = mid+1; i <= high; i++) {
        right[i-mid-1] = arr[i];
    }
    right[high - mid] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for (int k = low; k <= high; k++) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
    }
}