ソートアルゴリズムjava実装
6626 ワード
いくつかのソートアルゴリズム、私はアルゴリズムの偽コードに従ってjavaで実現して、最初はintタイプで、それから汎用型に変えました.
これはずいぶん前に書いたコードです.今は復習して、面接の準備をしていると思っています.
1.単純選択ソート
このアルゴリズムは最も簡単なものであるべきで、配列の中で最初から循環して、最も小さいものを最も前に置いて、これはよく実現してくだらないことを言わないべきです
中には汎用型が入っていて、TがComparableインタフェースを統合するということです.つまり、Tタイプは比較できるということです.
テストコードを書いて、main関数をつければいいです.
これはただ20個の数をテストして、10000に変えることができて、それから出力の注釈を落として、運行時間を計算して、異なるソートアルゴリズムの運行時間を比較します
2.選択ソートアルゴリズムの改善
簡単な選択ソートアルゴリズムを改善すると、毎回最大、最小を選択し、それぞれ配列の左右に置くので、ループはn/2しかできません.
3.ソートの挿入
与えられた配列の2番目の数からループを開始し、配列の前は整列しており、取り出した数を一度前の整列した数と後ろから前へ比較し、小さい頃はその数の位置を後ろに移動し、適切な位置を見つけて挿入することを知っている.
いいでしょう、言叶で私を表现するのはよくなくて、図のを使うべきで、しかしまだ図を描くことができません~~やはり直接コードに行って、とても简単なアルゴリズム、直接コードを见て大丈夫だと思います
退勤時間になったら、まずこの簡単なソートを一時的に記録します.
これはずいぶん前に書いたコードです.今は復習して、面接の準備をしていると思っています.
1.単純選択ソート
このアルゴリズムは最も簡単なものであるべきで、配列の中で最初から循環して、最も小さいものを最も前に置いて、これはよく実現してくだらないことを言わないべきです
public static <T extends Comparable<T>> T[] genericsimpleselectionsort(T[] a){
for (int i = 0; i < a.length; i++) {
int min = i;
int j = i + 1;
while (j < a.length) {
if (a[j].compareTo(a[min])<0)
min = j;
j++;
}
T temp = a[i];
a[i] = a[min];
a[min] = temp;
}
return a;
}
中には汎用型が入っていて、TがComparableインタフェースを統合するということです.つまり、Tタイプは比較できるということです.
テストコードを書いて、main関数をつければいいです.
public static void main(String[] args) {
Random random=new Random(47);
int n=20;
Integer[] a=new Integer[n];
for (int i = 0; i < a.length; i++) {
a[i]=random.nextInt(100);
System.out.print(a[i]+" ");
}
System.out.println();
Integer[] b=SimpleSelectSort.genericsimpleselectionsort(a);
for (int i = 0; i < b.length; i++) {
System.out.print(b[i]+" ");
}
}
これはただ20個の数をテストして、10000に変えることができて、それから出力の注釈を落として、運行時間を計算して、異なるソートアルゴリズムの運行時間を比較します
2.選択ソートアルゴリズムの改善
簡単な選択ソートアルゴリズムを改善すると、毎回最大、最小を選択し、それぞれ配列の左右に置くので、ループはn/2しかできません.
public static <T extends Comparable<T>> T[] genericselectionsort(T[] a) {
int n = a.length;
for (int i = 0; i < n / 2; i++) {
int min = i;
int max = i;
int j = i + 1;
while (j < n - i) {
if (a[j].compareTo(a[min]) < 0)
min = j;
if (a[j].compareTo(a[max]) > 0)
max = j;
j++;
}
T temp = a[i];
a[i] = a[min];
a[min] = temp;
temp = a[n - i - 1];
a[n - i - 1] = a[max];
a[max] = temp;
}
return a;
}
3.ソートの挿入
与えられた配列の2番目の数からループを開始し、配列の前は整列しており、取り出した数を一度前の整列した数と後ろから前へ比較し、小さい頃はその数の位置を後ろに移動し、適切な位置を見つけて挿入することを知っている.
いいでしょう、言叶で私を表现するのはよくなくて、図のを使うべきで、しかしまだ図を描くことができません~~やはり直接コードに行って、とても简単なアルゴリズム、直接コードを见て大丈夫だと思います
public static <T extends Comparable<T>> T[] genericInsertSort(T[] a) {
for (int i = 1; i < a.length; i++) {
int j = i;
T temp = a[j];
while (j > 0) {
if (temp.compareTo(a[j - 1]) < 0) {
a[j] = a[j - 1];
j--;
} else {
break;
}
}
a[j] = temp;
}
return a;
}
退勤時間になったら、まずこの簡単なソートを一時的に記録します.