首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >合并排序Java

合并排序Java
EN

Stack Overflow用户
提问于 2009-11-15 06:39:56
回答 7查看 24.8K关注 0票数 3

我正在尝试创建一个合并排序方法,但它总是给出错误的排序。我在哪里有改变,使它真正排序的数组?代码的哪一部分必须有所不同?谢谢您抽时间见我。

代码语言:javascript
复制
  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;   
     }

编辑:现在mergeSort并不是真的对数字进行排序,谁能告诉我它具体在哪里?尤其是当我打印“测试合并排序”部分时。

EN

回答 7

Stack Overflow用户

发布于 2012-12-03 21:36:59

代码语言:javascript
复制
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 + ", ");
        }
    }
}
票数 3
EN

Stack Overflow用户

发布于 2013-08-28 03:48:34

这是另一个!

代码语言:javascript
复制
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;
}
票数 0
EN

Stack Overflow用户

发布于 2013-12-24 03:31:03

代码语言:javascript
复制
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++;
        }
    }
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/1735863

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档