使用插入排序和归并排序的混合排序

Question

我希望实现一种混合算法，一旦输入数组大小变得太大，它就会从插入排序切换到归并排序。

这是我的主要功能（我目前将输入数组大小固定为 30，因为我想测试我的合并排序功能）：

    public static void main(String[] args) { 
        int[] a = genrandarray(30);
        
        long bgn, end;
        bgn = System.currentTimeMillis();
        
        imsort(a, 0, a.length, 30);
        
        end = System.currentTimeMillis();
        
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

当数组大小<20时调用插入排序，否则调用归并排序：

    public static void imsort(int [] slot, int b, int e, int size) {
        
        //if smaller than 20, use insertion sort
        if (e-b<=20) {
            insertionSort(slot, e);  //e is the length of slot[]
            System.out.println("imsort entered!");
        }
        

        else {
            mergesort(b, e, slot);
            
            System.out.println("mergesort entered!");
        }
    }

目前我的合并排序函数出现索引 30 越界错误。

    public static int merge(int n, int m, int[] slot) {
        int mid = (n+m)/2;
        int a = n, b = mid+1, i, tmp, cmp=0, comp=0;
        
        //sanity check 
        if (m-n <= 0) return -1000;
        
        while (a <= mid && b <= m) {
            cmp = compare(slot[a], slot[b]); 
            comp++;
            
            if (cmp > 0) { //slot[a] > slot[b]
                tmp = slot[b++];
                for (i = ++mid; i > a; i--)
                    slot[i] = slot[i-1];
                    slot[a++] = tmp;
            } 
            
            else if (cmp < 0) //slot[a] < slot[b] 
                    a++;
            
            else {
                //slot[a] == slot[b]
                if (a == mid && b == m) break;
                tmp = slot[b++];
                a++;
                for (i = ++mid; i > a; i--)
                slot[i] = slot[i-1]; slot[a++] = tmp;
            }
        } // end of while loop;
        
        return comp;
    } // end of merge

    public static int mergesort(int s, int e, int[] slot) {
        //int comp =0;
        int mid = (s+e)/2;  
        int right=0, left=0;
        
        if(e-s>0) {
            //comp++;
            left = mergesort(s,mid, slot);
            //comp++;
            right = mergesort(mid+1,e, slot);
        }
        return right + left + merge(s,e,slot);
    }

我不确定我的合并/合并排序函数中的错误。我可以得到一些进一步的建议吗？

Answer 1

a.length returns 你 30 我相信这是来自 genrandarray 方法的随机数组的长度。你的数组索引为 0 到 29。尝试像这样更改主要方法，它会成功

public static void main(String[] args) { 
        int[] a = genrandarray(30);
        
        long bgn, end;
        bgn = System.currentTimeMillis();
        
        imsort(a, 0, a.length-1, 30);
        
        end = System.currentTimeMillis();
        
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

Answer 2

首先，让我祝贺一个非常好的 post 新人。您没有post发生错误的代码行并且代码不完整，所以我填写了一些空白并执行了它：

import java.util.Arrays;
import java.util.Random;

public class Test {

    public static int[] genrandarray(int n)
    {
        int[] a = new int[n];
        Random r = new Random();
        for(int i=0;i<n;i++) a[i] = r.nextInt();
        return a;
    }
    
    public static void main(String[] args) { 
        int[] a = genrandarray(30);
        
        long bgn, end;
        bgn = System.currentTimeMillis();
        
        imsort(a, 0, a.length, 30);
        
        end = System.currentTimeMillis();
        
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }

    public static void imsort(int [] slot, int b, int e, int size) {
        
        //if smaller than 20, use insertion sort
        if (e-b<=20) {
            Arrays.sort(slot, 0, e);
           System.out.println("imsort entered!");
        }
        

        else {
            mergesort(b, e, slot);
            
            System.out.println("mergesort entered!");
        }
    }

    public static int merge(int n, int m, int[] slot) {
        int mid = (n+m)/2;
        int a = n, b = mid+1, i, tmp, cmp=0, comp=0;
        
        //sanity check 
        if (m-n <= 0) return -1000;
        
        while (a <= mid && b <= m) {
            cmp = slot[a] - slot[b]; 
            comp++;
            
            if (cmp > 0) { //slot[a] > slot[b]
                tmp = slot[b++];
                for (i = ++mid; i > a; i--)
                    slot[i] = slot[i-1];
                    slot[a++] = tmp;
            } 
            
            else if (cmp < 0) //slot[a] < slot[b] 
                    a++;
            
            else {
                //slot[a] == slot[b]
                if (a == mid && b == m) break;
                tmp = slot[b++];
                a++;
                for (i = ++mid; i > a; i--)
                slot[i] = slot[i-1]; slot[a++] = tmp;
            }
        } // end of while loop;
        
        return comp;
    } // end of merge   

    public static int mergesort(int s, int e, int[] slot) {
        //int comp =0;
        int mid = (s+e)/2;  
        int right=0, left=0;
        
        if(e-s>0) {
            //comp++;
            left = mergesort(s,mid, slot);
            //comp++;
            right = mergesort(mid+1,e, slot);
        }
        return right + left + merge(s,e,slot);
    }
}

该错误是由于在您的合并函数中将变量 a 设置为 n，然后在行 cmp = slot[a] - slot[b] 中设置的。因为数组从0到n-1，n会导致越界异常。

使用插入排序和归并排序的混合排序

Hybrid sorting using insertion sort and merge sort

java

sorting

mergesort

insertion-sort