Arrays.sort (Object [] a) - được triển khai như thế nào?

Question

Có tài nguyên nào về cách mergeSort được sử dụng bởi Arrays.sort (Object [] a) được triển khai không? Trong khi nó được ghi nhận khá tốt, tôi có một thời gian khó hiểu nó (đặc biệt là tại sao src và dest được chuyển đổi khi mergeSort() nhận được đệ quy gọi).

Answer 1

Here is the source trong số java.util.Arrays.

Thực ra, bạn có mã nguồn đó trong JDK - chỉ cần mở java.util.Arrays trong IDE của bạn và mã nguồn + nhận xét sẽ xuất hiện. Nếu bạn không có IDE, hãy xem JDK_HOME\src.zip

Sau đó, hãy đặt nó trong IDE của bạn và theo dõi cách hoạt động.

• breakpoint đặt (và chạy một chương trình trong chế độ gỡ lỗi)
• sử dụng System.out.println(..)
• phần thay đổi của nó để xem cách họ được phản ánh.
• đọc được sự chú ý wikipedia article about merge sort
• trả tiền để nhận xét này: // Recursively sort halves of dest into src

Answer 2

Tôi từng có sự nhầm lẫn tương tự với bạn. Theo hiểu biết của tôi, lý do cho việc chuyển đổi này rất đơn giản - thực hiện theo bước kết hợp dễ dàng hơn. Không có phép thuật.

private static void mergeSortWithoutSwitch(Object[] src, Object[] dest, int low, int high, int off) { 
    int length = high - low; 

    // Insertion sort on smallest arrays 
    if (length < INSERTIONSORT_THRESHOLD) { 
     for (int i = low; i < high; i++) 
      for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) 
       swap(dest, j, j - 1); 
     return; 
    } 

    // Recursively sort halves of dest into src 
    int destLow = low; 
    int destHigh = high; 
    low += off; 
    high += off; 
    int mid = (low + high) >>> 1; 
    mergeSortWithoutSwitch(src, dest, low, mid, off); 
    mergeSortWithoutSwitch(src, dest, mid, high, off); 

    // If list is already sorted, just copy from src to dest. This is an 
    // optimization that results in faster sorts for nearly ordered lists. 
    if (((Comparable) dest[mid - 1]).compareTo(dest[mid]) <= 0) { 
     return; 
    } 

    // Merge sorted halves (now in src) into dest 
    for (int i = destLow, p = low, q = mid; i < destHigh; i++) { 
     if (q >= high || p < mid && ((Comparable) dest[p]).compareTo(dest[q]) <= 0) 
      src[i] = dest[p++]; 
     else 
      src[i] = dest[q++]; 
    } 

    // copy back 
    for (int i = destLow; i < destHigh; i++) { 
     dest[i] = src[i]; 
    } 

} 

Trên đây là việc triển khai mà không cần chuyển đổi, từ mã, bạn có thể thấy chúng tôi cần thêm một bước nữa khi sao chép - sao chép lại. Tôi nghĩ rằng việc đặt tên tham số trong mergeSort là một chút nhầm lẫn, vì src là mảng phụ chỉ được sử dụng trong bước sáp nhập, nên tốt hơn nên đặt tên nó bằng aux (Chúng ta thậm chí có thể loại bỏ nó khỏi chữ ký phương thức và tạo một biến cục bộ khi hợp nhất). Và dest là mảng kết quả.