复杂度图表

1. 冒泡排序
   每次相邻两个数字进行比较，将大的数字交换到后一个，然后继续操作，一直把本趟最大数字放在最后，完成了一趟，接着对前n-1个数字进行相同的交换操作，将次大的数字放在倒数第二位的位置......一直到所有数字都排列好。
   时间复杂度O(n^2)

public class Solution {

    public static void main(String[] args) {
        int nums1[] = new int[]{10, 5, 2, 6};
        int n = nums1.length;
        for (int i = 0; i < n - 1; i++) {           // N个数字，N-1趟排序
            for (int j = 0; j < n - 1 - i; j++) {   // 每趟需要N-1-i次比较/交换
                int t = nums1[j];
                nums1[j] = nums1[j + 1];
                nums1[j + 1] = t;
            }
        }
    }
}

1. 选择排序
   首先通过n-1次比较，从n个数字中找到最小的数，将它和第一个数字交换—第一趟选则排序，结果最小的被安置在第一个位置。
   再通过n-2次比较，从剩余的n-1个数字找到次小的数，将它与第二个数交换—第二趟选则排序，结果次小的被安置在第二个位置。
   重复上述过程......
   通过n-1趟排序后完成。

public class Solution {

    public static void main(String[] args) {
        int nums1[] = new int[]{10, 5, 2, 6};
        int n = nums1.length;

        int i, j, t, k = 0;
        for (i = 0; i < n - 1; i++) {       // N个数字需要N-1趟排序
            k = i;                          // 本趟排序的N-i个数的第一个数下标为i，k是本趟要找的最小数字的下标
            for (j = i + 1; j < n; j++) {
                if (nums1[k] > nums1[j]) {
                    k = j;
                }
            }

            t = nums1[k];                   // 将找到到的最小元素放在最前面
            nums1[k] = nums1[i];
            nums1[i] = t;
        }
    }
}

1. 插入排序
   插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
   插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

public class Solution {

    public static void main(String[] args) {
        int nums1[] = new int[]{10, 5, 2, 6};
        int n = nums1.length;

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < nums1.length; i++) {

            // 记录要插入的数据, i是未排序的数的下标
            int need = nums1[i];

            // 从已经排序的序列最右边排好序第一个的开始比较，找到比其小的数
            int j = i - 1;
            while (j >= 0 && need < nums1[j]) {
                nums1[j + 1] = nums1[j];
                j--;
            }

            // 插入
            if (j != i - 1) {
                nums1[j + 1] = need;
            }
        }

    }
}

1. 希尔排序 一般不做要求, 可以参考wiki。

2. 堆排序
   　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
   堆
   　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。
   下面为了方便都以大根堆为例:
   

堆的实现
在实现堆之前先定义两种操作，称为上浮(swim)和下沉(sink)。先假设我们有一个有序的二叉堆，然后由于不知道什么原因，某个元素发生了变化造成了整个堆不是有序的了。那么，我们可以通过上浮和下沉重新让堆变成有序的。

上浮
如果一个元素突然变得比他的父节点大，那么他就需要上浮。因为假设其他部分都是有序的，那么，交换该节点和它的父节点，现在这个结点的子树是堆有序的。因为该节点大于其父节点，而父节点又大于他的另一个子节点，那么交换后的这个节点大于它的两个子节点，这两个子节点的子树一定也是堆有序的，那么可知该节点的子树是堆有序的。然后观察该节点是否还是比其父节点小，是的话再继续交换上浮，直到他比其父节点小。由上面的证明可知此时的整个堆是有序的。

private void swim(int k) {
    // k <= 1没必要swim
    while (k > 1 && pq[k / 2] < pq[k]) {
        exchage(k / 2, k);
        k = k / 2;
    }
}

下沉
下沉原理上和上浮类似，当一个元素比其子节点小的时候，交换该节点和这个更大的子节点。证明就略过，可以知道，当一个节点下沉到他比最大的子节点都大的时候这个堆是有序的。值得注意的是每次sink()都要进行两次比较，一次是找出更大的子节点，一次是判断是否比更大的子节点大。

private void sink(int k) {
    // 有左儿子
       while (2 * k <= N) {
        int t = 2 * k;
        if (t < N && pq[t] < pq[t + 1]) {
            // 说明右儿子2 * K + 1更大
            t++;
        }
        if (pq[k] >= pq[t]) {
            break;
        }
        exchage(k, t);
        k = t;
    }
}

全部代码:

class MaxPQ {

    int [] pq;      // 完全二叉树，存放数值
    int N = 0;      // 数值存储在pq[1...N]中,pq[0]没有使用

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

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

    public int getSize() {
        return N;
    }

    private void exchage(int i, int j) {
        int tmp = pq[i];
        pq[j] = pq[i];
        pq[i] = tmp;
    }

    public void add(int v) {
        pq[++N] = v;
        swim(N);
    }

    private void swim(int k) {
        // k <= 1没必要swim
        while (k > 1 && pq[k / 2] < pq[k]) {
            exchage(k / 2, k);
            k = k / 2;
        }
    }

    public int remove() {
        int head = pq[1];       // heap头是最大元素
        exchage(1, N--);     // 和最后一个节点位置交换
        pq[N + 1] = 0;          // 恢复默认值,之前N--了
        sink(1);             // 维护堆有序性
        return head;
    }

    private void sink(int k) {
        // 有左儿子
        while (2 * k <= N) {
            int t = 2 * k;
            if (t < N && pq[t] < pq[t + 1]) {
                // 说明右儿子2 * K + 1更大
                t++;
            }
            if (pq[k] >= pq[t]) {
                break;
            }
            exchage(k, t);
            k = t;
        }
    }

}

1. 计数排序
   计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序适用于数据范围不大且确定数据范围时候进行排序。

public class Solution {

    public static void main(String[] args) {
        int nums1[] = new int[] {10, 5, 2, 6, 0};

        // 假设对<=100的数字进行排序
        int[] cnt = new int[101];
        for (int i = 0; i < nums1.length; i++) {
            cnt[nums1[i]]++;
        }

        int k = 0;
        for (int v = 0; v < 101; v++) {
            while (cnt[v] > 0) {
                nums1[k++] = v;
                cnt[v]--;
            }
        }


    }

}

1. 桶排序
   桶排序 (Bucket sort)原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。
   假设从[0, 20亿]数字进行排序，我们可以先对这些数字按照一定范围划分成一个个桶,[0…1999999]-[2000000…3999999]…
   
   所以桶排序适用于
   排序过程：

1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3.将各个桶中的数据有序的合并起来

1. 基数排序
   基数排序是将待排序的元素拆分为kk个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第kk关键字进行稳定排序，再对第k−1k−1关键字进行稳定排序，再对第k−2k−2关键字进行稳定排序……最后对第一关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。
   动画图:
   

2. 快速排序
   基本思想
   快速排序（QuickSort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：

1. 从要排序的数据中取一个数为“基准数”。
2. 通过一趟排序将要排序的数据分割成独立的两部分，其中左边的数据都比“基准数”小，右边的数据都比“基准数”大。并且左部分数组都小于左部分数组！
3. 然后再按步骤2对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class Solution {

    public static void main(String[] args) {
        int nums1[] = new int[] {10, 5, 2, 6, 0};
        quickSort(nums1, 0, nums1.length - 1);
    }

    public static void quickSort(int[] a, int l, int r) {
        if (l >= r) {
            // 不需要操作
            return;
        }
        // 分割点可以选第一个数字，可以选第二个数字，也可以random一个a数组的数字，也可以使用median three选一个
        int pivot = a[l], i = l - 1, j = r + 1;
        while (i < j) {
            do {
                i++;
            } while (pivot > a[i]);

            do {
                j--;
            } while (pivot < a[j]);

            // 指针没有相遇
            if (i < j) {
                swap(a, i, j);
            }
        }

        quickSort(a, l, j);
        quickSort(a, j + 1, r);
    }

    private static void swap(int[] a, int i, int j) {
        a[i] ^= a[j];
        a[j] ^= a[i];
        a[i] ^= a[j];
    }
}