クイックソート、スタックソート、挿入方法の比較

クイックソートと挿入法網に紹介されていますが、スタックソートはまだ分からないので、簡単にテストしてみましたが、実際には、クイックソートの性能が一番いいです.
その後、スタックのソートを理解してから、ドキュメントを書いて復習しやすいようにします.
————————————————————————————————————————————————————————
2017/11/28試験例、百万レベルの使用例、挿入法の時間性能はあまりにも悪い.配列サイズは自分で設定できます.

public class Sort {
    public static void main(String[] args) {

        int[] arr = new int[100000];
        Random r = new Random();
        for (int i = 0; i <100000 ; i++) {
            arr[i] = r.nextInt(1000000000);
        }
        int[] arr1 = arr.clone();
        int[] arr2 = arr.clone();
        // 
        long time = System.currentTimeMillis();
        quickSort(arr1,0,arr1.length-1);
        time = System.currentTimeMillis() - time;
        System.out.println(" "+time);

        // 
        time = System.currentTimeMillis();
        heapSort(arr2);
        time = System.currentTimeMillis() - time;
        System.out.println(" "+time);

        // 
        time = System.currentTimeMillis();
        insertSort(arr);
        time = System.currentTimeMillis() - time;
        System.out.println(" "+time);



/*        // 
        int[] arrs = new int[]{56, 18, 6, 3, 97, 66, 8, 26, 88, 30, 99, 93};
        //int[] arrs = new int[]{20,50,20,40,70,10,80,30,60};
        insertSort(arrs);
        quickSort(arrs,0,arrs.length-1);
        heapSort(arrs);
        System.out.println(Arrays.toString(arrs));*/

/*        // 
        for (int i = 0; i <100000 ; i++) {
            if(arr[i]!=arr1[i]&&arr1[i]!=arr2[i]){
                System.out.println(" "+arr[i]+arr1[i]+arr[2]);
                break;
            }
            if(i==arr1.length-1){
                System.out.println(" ");
            }
        }*/

}
public static void
heapSort(
int []arr){
//1.
大屋根の構築
for(
int i=arr.
length/
2-
1
;i>=
0
;i--){
//
最初の非葉接点から下から上へ、右から左へ構造を調整
adjustHeap(arr
,i
,arr.
length)
;
}
//2.
スタック構造の調整
+
スタックトップ要素と末尾要素の交換
for(
int j=arr.
length-
1
;j>
0
;j--){
swap(arr
,
0
,j)
;
//
スタックトップ要素と末尾要素を交換
adjustHeap(arr
,
0
,j)
;
//
スタックの再調整
} }
public static void
adjustHeap(
int []arr
,int i
,int length){
int temp = arr[i]
;
//
現在の要素を先に取り出します
i
for(
int k=i*
2+
1
;k;k=k*
2+
1){
//
から
i
結点の左の結点から、つまり
2i+1
で始まる
if(k+
11]){
//
左サブノードが右サブノードより小さい場合、
k
右サブノードへ
k++
;
}
if(arr[k] >temp){
//
子ノードが親ノードより大きい場合は、子ノードの値を親ノードに割り当てます(交換する必要はありません).
arr[i] = arr[k]
;
i = k
;
}
else{
break;
} } arr[i] = temp
;
//
将
temp
値を最終位置に配置
}
public static void
swap(
int []arr
,int a
,int b){
int temp=arr[a]
;
arr[a] = arr[b]
;
arr[b] = temp
;
}
private static void
quickSort(
int[] arr
,int left
,int right){
if(left>right){
return;
}
int p = arr[left]
;
int i= left
,j=right
;
while(iwhile(arr[j]>=p&&i;
}
while(arr[i]<=p&&i;
}
if(iint temp = arr[i]
;
arr[i] = arr[j]
;
arr[j] = temp
;
} } arr[left] = arr[i]
;
arr[i] = p
;
quickSort(arr
,left
,i-
1)
;
quickSort(arr
,i+
1
,right)
;
}
private static void
insertSort(
int[] arr) {
if(arr==
null || arr.
length ==
0){
return;
}
for (
int i =
0
; i length
; i++) {
int temp = arr[i]
;
int j = i-
1
;
while(j>=
0&&arr[j]>temp){ arr[j+
1] = arr[j]
;
j--
;
} arr[j+
1] = temp
;
} }}
結果は次のとおりです.
高速排出時間25 msスタック排出時間34 ms挿入法時間6500 msアルゴリズム並べ替え結果一致
ランダムに生成された配列(絶対的な原因)に基づいて時間が変動する複数回の測定.