ソートアルゴリズムjava実装

6626 ワード

いくつかのソートアルゴリズム、私はアルゴリズムの偽コードに従ってjavaで実現して、最初はintタイプで、それから汎用型に変えました.
これはずいぶん前に書いたコードです.今は復習して、面接の準備をしていると思っています.
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;

    }

 
退勤時間になったら、まずこの簡単なソートを一時的に記録します.