排序算法 java实现

几个排序算法，我是按照算法的伪代码用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.插入排序

从给的数组的第二个数开始循环，数组前面是排好的，将取出的数一次跟前面排好序的数从后向前比较，小就将该数的位置后移，知道找到合适的位置插入

好吧，用语言表达我说不好，应该用图的，但是还不会画图~~还是直接上代码把，很简单的算法，直接看代码应该没问题

    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;
    }

到下班时间了，先暂时记录这几个简单的排序

排序算法 java实现

相关推荐