0

だから私はMergeSortアルゴリズムを持っていて、MergeSortと挿入ソートを組み合わせてマージのオーバーヘッドを減らしたいのですが、問題はどのようにですか？挿入ソートを使用してセグメントをソートしてからマージしたい。

 public class mergesorttest{
    public static void main(String[]args){
        int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};
        mergeSort(d,0,d.length);
        for(int x:d) System.out.print(x+" "); 
        System.out.println(); 
    }

static void mergeSort(int f[],int lb, int ub){
    //termination reached when a segment of size 1 reached -lb+1=ub
    if(lb+1<ub){
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

static void merge (int f[],int p, int q, int r){
    //p<=q<=r
    int i =p; int j = q; 
    //use temp array to store merged sub-sequence
    int temp[] = new int[r-p]; int t = 0; 
    while(i<q && j<r){
        if(f[i]<=f[j]){
            temp[t] =f[i]; 
            i++;t++;
        }
        else{
            temp[t] = f[j];
            j++;
            t++;
        }

        //tag on remaining sequence
        while(i<q){
            temp[t] = f[i];
            i++;
            t++;

        }
        while(j<r){
            temp[t]=f[j];
            j++;
            t++;
        }
        //copy temp back to f
        i=p;t=0;
        while(t<temp.length){
            f[i]=temp[t];
            i++;
            t++;
        }
        }
}
}

public static void insertion_srt(int array[], int n, int b){
  for (int i = 1; i < n; i++){
  int j = i;
  int B = array[i];
  while ((j > 0) && (array[j-1] > B)){
  array[j] = array[j-1];
  j--;
  }
  array[j] = B;
  }
  }
4

2 に答える 2

11

マージにより、要素の並べ替えが自動的に処理されます。ただし、リストがあるしきい値を下回った場合は、挿入ソートを使用してソートできます。

static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
    if (ub - lb <= THRESHOLD)
        insertionSort(f, lb, ub);
    else
    {
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

これ以外のことを行うと（しきい値を少し変更することを除いて）、マージソートにかかる時間が長くなります。

マージソートはO（n log n）であり、挿入ソートはO（n 2）ですが、挿入ソートは定数が優れているため、非常に小さい配列では高速です。これ、これ、これ、そしてこれは私が見つけたいくつかの関連する質問です。

于 2013-02-25T08:35:01.970 に答える
4 
public static final int K = 5;

public static void insertionSort(int A[], int p, int q) {
    for (int i = p; i < q; i++) {
        int tempVal = A[i + 1];
        int j = i + 1;
        while (j > p && A[j - 1] > tempVal) {
            A[j] = A[j - 1];
            j--;
        }
        A[j] = tempVal;
    }
    int[] temp = Arrays.copyOfRange(A, p, q +1);
    Arrays.stream(temp).forEach(i -> System.out.print(i + " "));
    System.out.println();
}

public static void merge(int A[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int[] LA = Arrays.copyOfRange(A, p, q +1);
    int[] RA = Arrays.copyOfRange(A, q+1, r +1);
    int RIDX = 0;
    int LIDX = 0;
    for (int i = p; i < r - p + 1; i++) {
        if (RIDX == n2) {
            A[i] = LA[LIDX];
            LIDX++;
        } else if (LIDX == n1) {
            A[i] = RA[RIDX];
            RIDX++;
        } else if (RA[RIDX] > LA[LIDX]) {
            A[i] = LA[LIDX];
            LIDX++;
        } else {
            A[i] = RA[RIDX];
            RIDX++;
        }
    }
}

public static void sort(int A[], int p, int r) {
    if (r - p > K) {
        int q = (p + r) / 2;
        sort(A, p, q);
        sort(A, q + 1, r);
        merge(A, p, q, r);
    } else {
        insertionSort(A, p, r);
    }
}

public static void main(String string[]) {
    int[] A = { 2, 5, 1, 6, 7, 3, 8, 4, 9 };
    sort(A, 0, A.length - 1);
    Arrays.stream(A).forEach(i -> System.out.print(i + " "));
}
于 2016-10-20T15:42:41.267 に答える