如题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
迷茫2017-04-18 09:08:24
1. int[] a の場合、変数 a はオブジェクト参照であり、配列オブジェクトのアドレスをヒープに保存すると理解できます (配列内の特定の要素はヒープに保存されます)。 .sort() 変数 a の参照値が渡されます。これは、1 で述べたヒープ内の配列のアドレス値です。もちろん、a の値を使用して、ヒープ内の配列にアクセスできます。プログラムは配列内の要素の値と順序を変更できます。
高洛峰2017-04-18 09:08:24
質問に答えるには、DualPivotQuicksort.sort() メソッドを使用しているソース コードにアクセスしてください:
リーリーint[]work 一時配列は、ソート処理中にデータを保存するために使用されます。ソート後、元の配列 int[]a の内容は確実に変更されます。
さらに、Arrays.sort() メソッドに関しては、次の指示があります。
1. すべてのタイプのソートは Java 配列で提供されます。主に 8 つの基本データ型とオブジェクトの 2 つのカテゴリに分類されます。
2.Java は、プリミティブ (int、float、その他のプロトタイプ データ) 配列にはクイック ソートを使用し、オブジェクト配列にはマージ ソートを使用します。オブジェクトを分類する場合、安定性が重要です。たとえば、成績証明書は最初に学生番号に従って配置されているとします。次に、成績が同じであっても、張三が最初に李四の前にいたことを確認する必要があります。李四には行けません。 4人の後ろに行きます。そしてクイックソートは不安定です。オブジェクト配列に格納されるのはオブジェクトの参照だけであるため、複数のシフトによって追加のオーバーヘッドが発生することはありません。ただし、オブジェクト配列は一般に比較の回数に影響され、オブジェクトの比較の方がはるかにコストがかかる可能性があります。単純な数値の比較よりも。この点では、マージ ソートはクイック ソートよりも優れた機能を果たします。これが、マージ ソートをオブジェクト ソートとして選択する重要な理由の 1 つです。
3. ソートの最適化: 実装では、クイック ソートとマージの両方が再帰的です。つまり、ソートされる配列の長さが 7 未満の場合、代わりにバブル ソートが直接使用されます。再帰的に。分析: 長さ 6 の配列のバブル ソートの合計比較数は最大 1+2+3+4+5+6=21 で、最良の場合、比較は 6 回のみです。クイックソートやマージは再帰呼び出しなどのオーバーヘッドがあり、nが小さいと時間効率が不利になるため、ここでもバブルソートを使用しますが、これもクイックソートにとって非常に重要な最適化です。
4. ソースコード内のクイックソートは、主に以下の点を最適化します。ソート対象の配列の要素数が少ない場合、ソースコード内のしきい値は 7 で、挿入ソートが使用されます。挿入ソートの時間計算量は 0(n^2) ですが、配列要素が小さい場合は、クイック ソートの再帰操作がパフォーマンスに影響するため、クイック ソートよりも挿入ソートの方が優れています。より良い選択は、分割要素 (基本要素) です。配列をほぼ 2 つの等しい部分に分割できるため、最悪のシナリオを回避できます。たとえば、配列が順序付けされている場合、最初の要素を分割要素として選択すると、アルゴリズムの時間計算量は O(n^2) に達します。
