排序算法总结

n^2的算法：冒泡排序，选择排序，插入排序
n^1.3的算法：希尔排序
nlogn的算法：归并排序、快速排序

//O(n) algorithms
    //桶排序

    //O(n2) algorithms
    //冒泡排序
    //遍历数组，对每个元素若比后继大，则下沉。每次循环确定最大的数，必被交换到最后
    public static void bubbleSort(Comparable[] a) {
        for (int i = a.length; i > 0; i--) {
            for (int j = 0; j < i - 1; j++) {
                if (!less(a[j], a[j + 1])) exch(a, j, j + 1);
            }
        }
    }

    //选择排序
    //每次遍历一遍数组，直接找出最小的，放到第i个
    public static void selectSort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i; j < a.length; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exch(a, i, min);
        }
    }

    //插入排序
    //每次外循环的递增意味着前i个数组成的有序数组的规模增大，不断增加i即排序完成
    //因为每次新增元素加入的是有序的数组，所以插入很容易
    public static void insertSort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (less(a[j + 1], a[j])) exch(a, j, j + 1);
            }
        }
    }

    //O(n1.3) algorithms
    //希尔排序
    //使用插入排序的想法，先找到一个序列，用序列中最大的可执行的数来做gap
    //使用这个gap找所有的子数组，分别排序
    //找序列中次大的数做gap，继续执行
    public static void shellSort(Comparable[] a) {
        int h = 1;
        while (h < a.length / 3) h = h * 3 + 1;//序列中最接近a长度的
        int pace;
        while (h >= 1) {
            //将数组变成h有序
            for (int i = h; i < a.length; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }

    }

    //O(n log n) algorithms
    //归并排序
    //中间做切分，两边分别排序完成时，再合并即可
    //合并使用辅助数组，易得
    //两边的排序用递归
    //lo和hi都为闭区间
    private static void merge(Comparable[] a, int lo, int mid, int hi, Comparable[] aux) {
        for (int i = 0; i < a.length; i++) {
            aux[i] = a[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int n = lo; n <= hi; n++) {
            if (i > mid) a[n] = aux[j++];
            else if (j > hi) a[n] = aux[i++];
            else if (less(a[i], a[j])) a[n] = aux[i++];
            else a[n] = aux[j++];
        }
    }

    public static void mergeSort(Comparable[] a, int lo, int hi) {
        Comparable[] aux = new Comparable[a.length];
        if (lo == hi) return;
        int mid = lo + (hi - lo) / 2;//mid是靠前的那个中间位置数
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi, aux);//如果在类中，则可以把aux放在类变量，从而在函数原型中省去aux
    }

    //选择排序
    //任意挑选一个元素（这里取首元素），放到最终位置，即使得左边都比它小，右边都比它大
    //然后对两边排序即可（递归）
    //任取易于操作的方式应该是先打乱数组（消除输入依赖），再取首元素
    public static void quickSort(Comparable[] a, int lo, int hi) {
        StdRandom.shuffle(a);
        if (lo >= hi || lo < 0 || hi >= a.length) return;
        //放好基准
        int index = lo;//基准位置
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[index]) && i > index) {
                exch(a, i, index);
                index = i;
            }
        }
        quickSort(a, lo, index - 1);
        quickSort(a, index + 1, hi);
    }

泛型的使用（下面是我的一个实现）

static class MyInt implements Comparable {
        public int data = 0;

        public int compareTo(Object o) {
            MyInt other = (MyInt) o;
            if (this.data < other.data) return -1;
            if (this.data == other.data) return 0;
            else return 1;
        }

        MyInt(int i) {
            this.data = i;
        }

        public String toString() {
            return String.valueOf(this.data);
        }
    }

    public static void sort(Comparable[] a) {
    }

    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    private static void exch(Comparable[] a, int b, int c) {
        if (b == c) return;
        Comparable t = a[b];
        a[b] = a[c];
        a[c] = t;
    }

    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }

测试代码：

public static void main(String args[]) {
        MyInt[] a = new Sort.MyInt[4];
        MyInt d = new MyInt(1);
        MyInt b = new MyInt(2);
        MyInt c = new MyInt(3);
        MyInt e = new MyInt(4);
        a[0] = b;
        a[1] = d;
        a[2] = e;
        a[3] = c;
        Sort.quickSort(a, 0, a.length - 1);
        //Sort.mergeSort(a, 0, a.length - 1);
        //Sort.shellSort(a);
        //Sort.insertSort(a);
        //Sort.selectSort(a);
        //Sort.bubbleSort(a);
        show(a);
    }