对于基础排序算法的简要总结

本文主要分析排序算法中的选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序，以及其部分优化方式，部分代码示例。当然快速排序算法是最快的通用排序算法，这使得其在java中的地位非凡，通常的ArrayList.sort()函数就是使用的快速排序。

在这之前，我们先声明两个方法：分别为比较大小与数据交换的方法。

final static boolean less(Comparable i, Comparable j) {
        return i.compareTo(j) < 0;
}

final static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
}

在排序中我们使用Comparable[]的数组进行排序，以便兼容其他类型的数组。

选择排序

快速排序是的思维是依次找到最小或最大的值，将这个值与我们所比较的值中的第一个或进行交换。这种算法的特点是：1、运行时间与输入无关，就算是输入有序运行时间也是差不多的；2、数据的移动是所有算法中最少的。

public static void selectionSort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i+1; j < N; j++) {
                if (less(a[j], a[min]))
                    min = j;
                exch(a, i, min);
            }
        }
    }

插入排序

插入排序的基本思路是在循环中将下标i之前的元素进行比较交换（这儿是不符合比较小或比较大的条件则交换）。这种算法对于有序或者比较有序的数组时效率较高。

public static void insertSort(Comparable[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            Comparable mi = a[i];
            boolean f = false;
            int j = i;
            for (; j > 0 && less(mi, a[j - 1]); j--) {
                a[j] = a[j - 1];
                f = true;
            }
            if (f) {
                a[j] = mi;
            }
        }
    }

在上述插入排序代码示例中，并没有每次比较交换相邻的两个元素，而是将较大的元素都向右移，也是每次循环中将比循环比较的最后一个元素的值大的元素都作右移操作，从而减少访问数组的次数。对于减少访问数组的次数，这点需要详细说明一下：对于普通的插入排序，是每次获取相邻两个元素的值进行比较交换，即每次循环都会获取2*i次数据，总的访问数组（即获取数组元素）的次数就是n*(n-1)次（n为数组的长度）；而对于优化后的插入排序，每次循环访问数组i+1次，总的访问数组(n-1)*(n+2)/2次，大约减少了一半的访问数组的次数。

而对于插入排序与选择排序的比较，主要是在数组有序或部分有序时，减少了交换的次数，从而对于部分有序或有序的数组较高。

希尔排序

希尔排序的思想是使数组中的任意间隔为h的元素都是有序的。相对于插入排序改变了原来的插入的顺序。从原来的相邻的两个元素交换改成现在相邻两个增量交换的排序（增量即间隔）。通过增量递减的方式重复排序，直到增量为1，使得原数组有序。（增量序列为一组递减的且最后一个元素为1的数组。）

public static void shellSort(Comparable[] a) {
        int N = a.length;
        for (int h = N / 2; h >= 1; h = h / 2) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
        }
    }

在示例中我是将增量/2得到之后的增量；当然这种增量序列不是最优的。在张连堂与张博的《希尔排序最佳增量序列研究》中做了一些分析并得到一种最优的增量序列：... 2^k -1, ... 15, 7, 3, 1。

希尔排序对于之前的排序算法是对于平方级的突破，权衡了子数组的规模与有序性使得其更加高效。

归并排序

归并排序分为原地归并、自顶向下、自底向上三种归并方式。但是最主要的思维也是归并，归并是将前后两端进行比较，将小的放上去，需要注意越界。而自顶向下是采用分治的思想，使用递归的方式进行归并。自底向上是采用相邻两个归并，在到相邻两组归并，刚好与自顶向下相反。

public static class Merge {
        private static Comparable[] aux;

        /*归并*/
        public static void merge(Comparable[] a, int lo, int mid, int hi) {
            int i = lo, j = mid + 1;
            for (int k = lo; k <= hi; k++) {
                aux[k] = a[k];
            }
            for (int k = lo; k <= hi; k++) {
                if (i > mid) a[k] = aux[j++];
                else if (j > hi) a[k] = aux[i++];
                else if (less(aux[j], aux[i])) a[k] = aux[j++];
                else a[k] = aux[i++];
            }
        }

        /*自顶向下*/
        public static void mergeTopSort(Comparable[] a) {
            aux = new Comparable[a.length];
            sort(a, 0, a.length-1);
        }

        private static void sort(Comparable[] a, int lo, int hi) {
            if (hi <= lo) return;
            int mid = lo + (hi - lo)/2;
            sort(a, lo, mid);
            sort(a, mid+1, hi);
            merge(a, lo, mid, hi);
        }

        /*自底向上*/
        public static void sort(Comparable[] a) {
            int N = a.length;
            aux = new Comparable[N];
            for (int sz = 1; sz < N; sz = sz+sz) {
                for (int lo = 0; lo < N -sz; lo += sz+sz) {
                    merge(a, lo, lo+sz+1, Math.min(lo+sz+sz-1, N-1));
                }
            }
        }
    }

快速排序

快速排序是最常用的排序算法，采用分治的思想。将一个数组分为两个数组再排序。

切分（partition）是使用交换等方法将某个值放确切的位置，再将其左右排序切分。这个确切的值满足其左边都小于它，右边都大于它，使得在其确定后，在整个排序过程中都不会对其产生影响，其位置不会再作变化。

final static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v)) {
                if (i == hi) break;
            }
            while (less(v, a[--j])) {
                if (j == lo) break;
            }
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

而排序算法就是使用递归的方式去调用切分的方法。

public static void quickSort(Comparable[] a, int lo, int hi) {
       if (hi <= lo) return;
       int j = partition(a, lo, hi);
       quickSort(a, lo, j - 1);
       quickSort(a, j + 1, hi);
   }

上述为标准快速排序，其在很多地方依然具有缺陷，如在切分不平衡时可能使得排序十分低效，如将{6, 5, 4, 3, 2, 1}转换成由小到大排序时就十分低效。

当然对于快速排序，先辈们依然做了许多优化的方法：1、快速排序对于小数组的排序特别慢，因此使用在数组小时以及分治到较小是采用插入排序优化；2、使用三取样切分，来解决具有大量重复数据情况。三取样切分的快速排序算法示例如下：

public static void quick3waySort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];
        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                exch(a, lt++, i++);
            } else if (cmp > 0) {
                exch(a, i, gt--);
            } else {
                i++;
            }
        }
        quick3waySort(a, lo, lt - 1);
        quick3waySort(a, gt + 1, hi);
    }

优先队列以及堆排序

顾名思义，是具有优先级的队列，即对于这个队列中的数据是有序的。实现方式有很多，基于数组、链表、堆都可以实现。这儿主要介绍一下基于二叉堆的优先队列的实现，下述代码中已经十分清晰。

public static class MaxPQ<Key extends Comparable<Key>> {
        private Key[] pq;
        private int N = 0;

        public MaxPQ(int maxN) {
            pq = (Key[]) new Comparable[maxN + 1];
        }

        public boolean isEmpty() {
            return N == 0;
        }

        public int size() {
            return N;
        }

        private boolean less(int i, int j) {
            return pq[i].compareTo(pq[j]) < 0;
        }

        private void exch(int i, int j) {
            Key t = pq[i];
            pq[i] = pq[j];
            pq[j] = t;
        }

        private void swim(int k) {
            while (k > 1 && less(k / 2, k)) {
                exch(k / 2, k);
                k /= 2;
            }
        }

        private void sink(int k) {
            while (2 * k <= N) {
                int j = 2 * k;
                if (j < N && less(j, j + 1)) {
                    j++;
                }
                if (!less(k, j)) {
                    break;
                }
                exch(k, j);
                k = j;
            }
        }

        public void insert(Key v) {
            pq[++N] = v;
            swim(N);
        }

        public Key delMax() {
            Key max = pq[1];
            exch(1, N--);
            pq[N + 1] = null;
            sink(1);
            return max;
        }
    }

需要注意的是上浮swim()和下沉sink()函数，是分别在插入与删除的时候被调用使得二叉堆平衡。

而堆排序算法如下：

public static void heapSort(Comparable[] a) {
            int n = a.length;
            for (int k = n/2; k >= 1; k--) {
                sink(a, k, n);
            }
            while (n > 1) {
                exch(a, 1, n--);
                sink(a, 1, n);
            }
        }

这儿的sink(i,j,N)也是下沉函数，是将从j为顶开始下沉操作，使得平衡，具体实现类似于之前的优先队列的sink函数。这儿的思想是得到最大数与最后一个数交换再对前面的数组进行下沉操作，以此类推。

总结

对于排序算法，我们需要分析其稳定性。在排序算法中保留重复元素的相对位置，则该算法是稳定的。对于目前的排序算法中，插入与归并排序是稳定的；而选择、希尔、快速、堆排序不是稳定的。

算法	是否稳定	是否原地排序	时间复杂度	空间复杂度	备注
选择排序	否	是	N^2	1
插入排序	是	是	介于N和N^2之间	1	取决于输入元素的排列情况
希尔排序	否	是		1
快速排序	否	是	N*logN	lgN	运行效率由概率提供保证
三切分快速排序	否	是	介于N和N*logN之间	lgN	运行效率由概率提供保证，同时取决于输入元素的分布情况
归并排序	是	否	N*logN	N
堆排序	否	是	N*logN	1

附

本文并没有涉及所有的排序算法，还有如冒泡排序、基数排序等，需要的可以找找资料学习。