-3

所以我不知道如何将 B 的元素复制到一个新的 SortPair 元素数组中，其中 int 组件是数组索引，例如：

B = [ (7,Q), (9,W), (5,K), (0,S), (9,B) ]<br>

将会 ：

P = [ {(7,Q),0}, {(9,W),1}, {(5,K),2}, {(0,S),3}, {(9,B),4} ]

然后使用带有派生比较器 sort_cmp 的 quickSort 对 P 进行排序

因此，如果 Element 部分相等，则通过数组索引进行比较；因此保持相同的相对顺序。

最后将P的Elements部分复制回B中，对于原格式为原B格式。

import MySorts.Algorithms;
import java.util.*;
import sorts.*;

public static void main(String[] args) {
   //mainCheckStability(args);
    mainMakeStableQuicksort(args);
    //mainTimeSorts(args);
}

public static void mainMakeStableQuicksort(String[] args){
    class Element{
        int int_part;
        char chr_part;
        Element(int int_part, char chr_part){
            this.int_part = int_part; this.chr_part = chr_part;
        }
        @Override
        public String toString() {return "(" + int_part + "," + chr_part +")";}
    }

    class SortPair{
        Element element;
        int index;

        SortPair(Element j, int i){
            this.index = i;
            this.element = j;}

        public String toString(){
            return ("(" + element.toString()+"'"+index+")");

        }
    }
    //Element [] j = new Element[20];
      //  int i = 0;

   final Comparator<Element> cmp = new Comparator<Element>(){
   @Override
   public int compare(Element lhs, Element rhs){
   return lhs.int_part - rhs.int_part;
        }
    };   


    Comparator<SortPair> sort_cmp = new Comparator<SortPair>(){
    @Override
    public int compare(SortPair lhs, SortPair rhs){
    int compt = cmp.compare(lhs.element,rhs.element);
        if(compt == 0)
            return(lhs.index-rhs.index);
        else{
            return(compt);
        }

        //return lhs.i - rhs.i;
        }
    };             

    Element [] Q = new Element[15];

    Random r = new Random();

    for (int i = 0; i <Q.length; ++i){
        int n = r.nextInt(10);
        char c = (char) (((int)'A')+ r.nextInt(26));
        Q[i] = new Element(n,c);
    }
    Element[] A = Arrays.copyOf(Q, Q.length);
    Element[] B = Arrays.copyOf(Q, Q.length);
    Element[] C = Arrays.copyOf(Q, Q.length);
    Element[] D = Arrays.copyOf(Q, Q.length);      

    Algorithms.setQuicksortCutoff(5);

    System.out.println("array:     "+ Arrays.toString(Q) + "\n");

    Algorithms.mergeSort(A, cmp);
    System.out.println("merge,full: " + Arrays.toString(A));             

    //i commented out the old command and this is where i believe i need to implement the Sort B array code
    //I just don't know how to add the int index, when copying B in to the New array P of SortPair, any help would be appreciated i should know this stuff by now 
    //Algorithms.quickSort(B, cmp);
    Element [] P = (Element[])B.clone(); 
    Element.SortPair(P, ){
    @Override
    public int compare(Element[] e1, Element[] e2){
        return
    }
}
    for(int i =< B.length ){

    }
       Element [] B =(Element[])P.clone()
    System.out.println("quick,full: " + Arrays.toString(P));
    System.out.println();

    int low = 3, high = Q.length - 3;

    System.out.println("array:   "+ Arrays.toString(Q) + "\n");

    Algorithms.mergeSort(C, low, high, cmp);
    System.out.println("merge,"+low+"-"+high+": "+ Arrays.toString(C));

    Algorithms.mergeSort(D, low, high, cmp);
    System.out.println("merge,"+low+"-"+high+": "+ Arrays.toString(D));


}
4

1 回答 1

0

我想通了@RST，感谢您在 //algorithms.quickSort(B, cmp); 之后的快速响应 需要以正确的格式获得适当的 stableQuickSort。 

SortPair[] P = new SortPair[B.length];

        for(int c = 0; P.length > c;c++ ){
            P[c] = new SortPair(B[c],c);
        }

    Algorithms.quickSort(P, sort_cmp);

     //System.out.println("quick,full: " + Arrays.toString(P));
    //System.out.println();

    for(int c = 0; B.length > c; c++){
        B[c] = new Element(P[c].element.int_part, P[c].element.chr_part);
    }
        System.out.println("Stable quickSort: " + Arrays.toString(B));
于 2013-05-13T14:10:47.067 回答