ヒルソートと挿入ソート、どちらが速いですか?
2309 ワード
マイヒルソートコード
挿入ソートコード
実行結果は次のとおりです.
ヒルソートの所要時間:26
0 1 2 3 4 5 6 7 8 9
===============
ソートの挿入に要した時間:5
0 1 2 3 4 5 6 7 8 9
ヒルソートはソートを挿入する改良版なので、どのように効率がソートを挿入するよりも低いのでしょうか.私のプログラムが間違っていますか?ご指導を請う
package sort;
import static print.Print.printhh;
import static print.Print.printsz;
public class ShellSort {
public static void main(String[] args) {
int[] data = {9,8,7,6,5,4,3,2,1,0};
ShellSort shellSort = new ShellSort();
long begin = System.currentTimeMillis();
for (int i = 0 ; i < 100000000 ; i++){
shellSort.sort(data);
}
long end = System.currentTimeMillis();
printhh (" :"+(end-begin)/1000);
printsz (data);
}
public void sort(int[] data){
for (int i = data.length/2 ; i > 0 ; i/=2)
for (int j = 0 ; j < i ; j++)
insertSort (data,j,i);
}
public void insertSort(int[] data , int start , int inc){
for (int i = start + inc ; i < data.length ; i += inc)
for (int j = i ; (j >= inc) && (data[j] < data[j-inc]) ; j -= inc)
swap(data,j,j-inc);
}
public void swap(int[] data , int i , int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
挿入ソートコード
package sort;
import static print.Print.*;
public class InsertSort {
public static void main(String[] args){
int[] data = {9,8,7,6,5,4,3,2,1,0};
InsertSort insertSort = new InsertSort();
long begin = System.currentTimeMillis();
for (int i = 0 ; i < 100000000 ; i++){
insertSort.sort(data);
}
long end = System.currentTimeMillis();
printhh (" :"+(end-begin)/1000);
printsz (data);
}
public void sort(int[] data){
for (int i = 1 ; i < data.length ; i++)
for (int j = i ; (j>0) && (data[j]<data[j-1]) ; j--)
swap(data,j,j-1);
}
public void swap(int[] data , int i , int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
実行結果は次のとおりです.
ヒルソートの所要時間:26
0 1 2 3 4 5 6 7 8 9
===============
ソートの挿入に要した時間:5
0 1 2 3 4 5 6 7 8 9
ヒルソートはソートを挿入する改良版なので、どのように効率がソートを挿入するよりも低いのでしょうか.私のプログラムが間違っていますか?ご指導を請う