java.util.Arrays.sort()数组形参传递为啥能修改原始数组的内容？

Question

如题java.util.Arrays.sort(int[] a)数组形参传递为啥能修改原始数组的内容？

[public static void sort(int[] a)](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[]))

Sorts the specified array into ascending numerical order.

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Parameters:a - the array to be sorted

Answer 1

1. For int[] a, variable a is an object reference, which can be understood as saving the address of the array object in the heap (specific elements in the array are saved in the heap);
2. Pass in variables in sort() The reference value of a is the address value of the array in the heap mentioned in 1. Using the value of a, of course, you can access the array in the heap, and then the program can modify the value and order of the elements in the array.

Answer 2

Because a copy of the original array address is passed in, the value of the original array can be changed.

Answer 3

To answer your question, go to the source code. It uses a method of DualPivotQuicksort.sort(). Click on this method:

static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen)

The int[]work temporary array is used to store data during the sorting process. After sorting, the contents of the original array int[]a will definitely be changed.
In addition, regarding the Arrays.sort() method, there are the following instructions:

1. Sorting of all types is provided in Java Arrays. It is mainly divided into two categories: 8 basic data types and Object.
2.Java uses quick sorting for Primitive (int, float and other prototype data) arrays and merge sorting for Object arrays. When it comes to sorting objects, stability is important. For example, the transcript may have been arranged according to the student number at the beginning. Now let's arrange it by grades. Then you should ensure that Zhang San was originally in front of Li Si. Even if their grades are the same, Zhang San cannot go to Li Si. Go behind the four. And quicksort is unstable. What is stored in the object array is only the reference of the object, so multiple shifts will not cause additional overhead. However, the object array is generally sensitive to the number of comparisons. It is possible that the comparison of objects is much more expensive than the comparison of simple numbers. Merge sort does a better job than quick sort in this regard, which is one of the important reasons for choosing it as an object sort.
3. Sorting optimization: In the implementation, both quick sort and merge are recursive. At the bottom of the recursion, that is, when the length of the array to be sorted is less than 7, bubble sort is used directly instead of recursively. Analysis: The total number of comparisons for bubble sorting of an array with a length of 6 is at most 1+2+3+4+5+6=21, and in the best case there are only 6 comparisons. Quick sort or merge involves the overhead of recursive calls, etc., and its time efficiency becomes more disadvantageous when n is small. Therefore, bubble sort is used here, which is also a very important optimization for quick sort.
4. The quick sort in the source code mainly optimizes the following aspects. When the number of elements in the array to be sorted is small, the threshold in the source code is 7, and insertion sort is used. Although the time complexity of insertion sort is 0(n^2), when the array elements are small, insertion sort is better than quick sort, because the recursive operation of quick sort affects performance. A better choice is the dividing element (basic element). Being able to split the array into roughly two equal parts avoids worst-case scenarios. For example, when the array is ordered, selecting the first element as the dividing element will make the time complexity of the algorithm reach O(n^2).

Answer 4

Except for String, objects in Java are all passed references.

Answer 5

What is modified is the reference value, which is int[] a, the value pointed by a,