Sắp xếp các mảng phù hợp trong Java

Question

Giả sử tôi có hai mảng (trong Java),

số int []; và int [] màu sắc;

Mỗi phần tử thứ i của các số tương ứng với phần tử thứ i của nó bằng màu sắc. Ví dụ, số = {4,2,1} màu = {0x11, 0x24, 0x01}; Có nghĩa là số 4 là màu 0x11, số 2 là 0x24, v.v.

Tôi muốn sắp xếp dãy số, nhưng sau đó vẫn có nó sao cho mỗi phần tử khớp với cặp màu của nó.

Ví dụ: số = {1,2,4}; màu = {0x01,0x24,0x11};

Cách sạch nhất, đơn giản nhất để thực hiện việc này là gì? Các mảng có một vài nghìn mục, do đó, được đặt ra sẽ là tốt nhất, nhưng không bắt buộc. Nó sẽ làm cho tinh thần để làm một Arrays.sort() và một so sánh tùy chỉnh? Sử dụng các hàm thư viện càng nhiều càng tốt là thích hợp hơn.

Lưu ý: Tôi biết giải pháp "tốt nhất" là tạo lớp cho hai phần tử và sử dụng trình so sánh tùy chỉnh. Câu hỏi này có nghĩa là yêu cầu mọi người biết cách nhanh nhất để viết mã này. Hãy tưởng tượng được ở một cuộc thi lập trình, bạn sẽ không muốn làm cho tất cả các lớp học thêm, các lớp học vô danh cho so sánh, vv Tốt hơn, quên Java; làm thế nào bạn sẽ mã nó trong C?

Answer 1

Bạn cần sắp xếp mảng màu theo mục tương đối của nó trong mảng số. Chỉ định một bộ so sánh so sánh các số và sử dụng nó làm so sánh cho mảng màu.

Answer 2

Tại sao không giới thiệu một đối tượng đại diện cho một số và màu sắc và thực hiện một hàm so sánh cho điều đó?

Ngoài ra, bạn có thực sự cần một mảng không, tại sao không sử dụng thứ gì đó có nguồn gốc từ Bộ sưu tập?

Answer 3

Có vẻ như điều sạch nhất cần làm là tạo lớp thuộc tính tùy chỉnh triển khai Comparable. Ví dụ:

class Color implements Comparable { 
    private int number; 
    private int color; 

    // (snip ctor, setters, etc.) 

    public int getNumber() { 
    return number; 
    } 
    public int getColor() { 
    return color; 
    } 

    public int compareTo(Color other) { 
    if (this.getNumber() == other.getNumber) { 
     return 0; 
    } else if (this.getNumber() > other.getNumber) { 
     return 1; 
    } else { 
     return -1; 
    } 
    } 
} 

Sau đó, bạn có thể tách thuật toán sắp xếp của bạn từ logic trật tự (bạn có thể sử dụng Collections.sort nếu bạn sử dụng một danh sách thay vì một mảng), và quan trọng nhất, bạn sẽ không phải lo lắng về cách nào đó nhận được hai mảng không đồng bộ.

Answer 4

Nếu bạn muốn được sẵn sàng bố trí thêm một số không gian, bạn có thể tạo mảng khác, gọi nó thêm, với các yếu tố như thế này:

extra = [0,1,...,numbers.length-1] 

Sau đó, bạn có thể sắp xếp mảng thêm này sử dụng Arrays.sort () với so sánh tùy chỉnh (điều đó, trong khi so sánh các phần tử i và j thực sự so sánh các con số [thêm [i]] và số [phụ [j]]). Bằng cách này sau khi sắp xếp mảng thừa, thừa [0] sẽ chứa chỉ mục của số nhỏ nhất và, vì số và màu không di chuyển, màu tương ứng.
Điều này không phải là rất tốt đẹp, nhưng nó được công việc làm, và tôi không thể thực sự nghĩ ra một cách dễ dàng hơn để làm điều đó.

Là một mặt lưu ý, trong cuộc thi này tôi thường tìm ra C++ cặp templated và bản đồ đẹp không thể thiếu;)

Answer 5

Bạn có thể sử dụng loại() với một so sánh tùy chỉnh nếu bạn giữ một mảng thứ ba với chỉ số, và được sắp xếp trên đó, để nguyên dữ liệu.

Java mã ví dụ:

Integer[] idx = new Integer[numbers.length]; 
for(int i = 0 ; i < idx.length; i++) idx[i] = i;    
Arrays.sort(idx, new Comparator<Integer>() { 
    public int compare(Integer i1, Integer i2) {       
     return Double.compare(numbers[i1], numbers[i2]); 
    }     
}); 

// numbers[idx[i]] is the sorted number at index i 
// colors[idx[i]] is the sorted color at index i 

Lưu ý rằng bạn phải sử dụng Integer thay vì int hoặc bạn không thể sử dụng một so sánh tùy chỉnh.

Answer 6

Tôi thích giải pháp @ tovare. Tạo một mảng con trỏ:

int ptr[] = { 1, 2, 3 }; 

và sau đó khi bạn sắp xếp theo số, hoán đổi các giá trị bằng ptr thay vì số. Sau đó truy cập thông qua mảng ptr, như

for (int i = 0; i < ptr.length; i++) 
{ 
    printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]); 
} 

Cập nhật: ok, có vẻ như những người khác đã đánh tôi. Không có XP cho tôi.

Answer 7

Có đủ để mã phương pháp sắp xếp của riêng bạn không? Một bong bóng đơn giản có lẽ sẽ nhanh chóng mã hóa (và nhận được ngay). Không cần thêm lớp hoặc so sánh.

Answer 8

Một lần hack nhanh sẽ là kết hợp hai mảng với sự dịch chuyển bit. Tạo một dãy các độ dài sao cho 32 bit quan trọng nhất là số và 32 bit nhỏ nhất là màu. Sử dụng phương pháp sắp xếp và sau đó giải nén.

Answer 9

Cách đơn giản nhất để thực hiện việc này trong C, sẽ là bong bóng + con trỏ kép. Ofcourse nhanh nhất sẽ là quicksort + hai con trỏ. Ofcourse con trỏ thứ 2 duy trì sự tương quan giữa hai mảng.

Tôi muốn xác định các giá trị được lưu trữ trong hai mảng dưới dạng cấu trúc và sử dụng cấu trúc trong một mảng. Sau đó sử dụng quicksort trên đó. bạn có thể viết phiên bản sắp xếp chung, bằng cách gọi hàm so sánh, có thể được viết cho mỗi cấu trúc, nhưng sau đó bạn đã biết rằng :)

Answer 10

Ví dụ minh họa bằng mảng chỉ mục thứ ba. Bạn không chắc chắn đây có phải là triển khai tốt nhất hay không.

 
    import java.util.*;
 

public class Sort { 

    private static void printTable(String caption, Integer[] numbers, 
       Integer[] colors, Integer[] sortOrder){ 

     System.out.println(caption+ 
       "\nNo Num Color"+ 
       "\n----------------"); 

     for(int i=0;i<sortOrder.length;i++){ 
      System.out.printf("%x %d  %d\n", 
        i,numbers[sortOrder[i]],colors[sortOrder[i]]); 

     } 
    } 


    public static void main(String[] args) { 

     final Integer[] numbers = {1,4,3,4,2,6}; 
     final Integer[] colors = {0x50,0x34,0x00,0xfe,0xff,0xff}; 
     Integer[] sortOrder = new Integer[numbers.length]; 

     // Create index array. 
     for(int i=0; i<sortOrder.length; i++){ 
      sortOrder[i] = i; 
     } 
     printTable("\nNot sorted",numbers, colors, sortOrder); 

     Arrays.sort(sortOrder,new Comparator<Integer>() { 
      public int compare(Integer a, Integer b){ 
       return numbers[b]-numbers[a]; 
      }}); 
     printTable("\nSorted by numbers",numbers, colors, sortOrder); 

     Arrays.sort(sortOrder,new Comparator<Integer>() { 
      public int compare(Integer a, Integer b){ 
       return colors[b]-colors[a]; 
      }}); 
     printTable("\nSorted by colors",numbers, colors, sortOrder); 
    } 
} 
 

Đầu ra nên trông như thế này:

 

Not sorted 
No Num Color 
---------------- 
0 1  80 
1 4  52 
2 3  0 
3 4  254 
4 2  255 
5 6  255 

Sorted by numbers 
No Num Color 
---------------- 
0 6  255 
1 4  52 
2 4  254 
3 3  0 
4 2  255 
5 1  80 

Sorted by colors 
No Num Color 
---------------- 
0 6  255 
1 2  255 
2 4  254 
3 1  80 
4 4  52 
5 3  0 

Answer 11

Sử dụng tín dụng TreeMap

Answer 12

-@tovare cho câu trả lời tốt nhất ban đầu.

câu trả lời của tôi dưới đây loại bỏ (bây giờ) autoboxing không cần thiết thông qua Maven phụ thuộc {net.mintern : primitive : 1.2.2} từ câu trả lời này: https://stackoverflow.com/a/27095994/257299

int[] idx = new int[numbers.length]; 
for(int i = 0 ; i < idx.length; i++) idx[i] = i; 
final boolean isStableSort = false; 
Primitive.sort(idx, 
       (i1, i2) -> Double.compare(numbers[i1], numbers[i2]), 
       isStableSort); 

// numbers[idx[i]] is the sorted number at index i 
// colors[idx[i]] is the sorted color at index i 

Answer 13

Tôi đoán bạn muốn tối ưu hóa hiệu suất trong khi cố gắng để tránh sử dụng mảng các đối tượng (mà có thể gây ra đau đớn Sự kiện GC). Thật không may là không có giải pháp chung, suy nghĩ. Nhưng, đối với trường hợp cụ thể của bạn, trong đó các con số khác nhau với nhau, có thể chỉ có hai mảng được tạo ra.

/** 
* work only for array of different numbers 
*/ 
private void sortPairArray(int[] numbers, int[] colors) { 
    int[] tmpNumbers = Arrays.copyOf(numbers, numbers.length); 
    int[] tmpColors = Arrays.copyOf(colors, colors.length); 
    Arrays.sort(numbers); 
    for (int i = 0; i < tmpNumbers.length; i++) { 
     int number = tmpNumbers[i]; 
     int index = Arrays.binarySearch(numbers, number); // surely this will be found 
     colors[index] = tmpColors[i]; 
    } 
} 

Hai mảng được sắp xếp có thể được thay thế bởi Int2IntOpenHashMap, thực hiện chạy nhanh hơn, nhưng sử dụng bộ nhớ có thể được tăng gấp đôi.