1. 冒泡排序
冒泡排序（Bubble Sort）是最简单的排序算法，在其执行过程中颇有贪心的韵味，通过每一步的最优处理达到最终结果的排序，为什么称其为冒泡排序，因为其像水泡相互挤压一样。
2.选择排序
选择排序（ Selection sort），顾名思义，每次遍历整个数组找到对应指针最小的数值。
3.插入排序
插入排序（Insertion Sort），从头至尾构建有序序列，每次从无序的部分中选出数据插入到有序序列中。如果是链表显示的逻辑线性表，那么我们无需逐个移动元素，但遍历链表找到插入节点的时间复杂度并不会减少。
4.希尔排序
希尔排序(Shell's Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort）。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序体现了一种分而治之的思想，通过大分组的排序来降低小分组排序的压力。
5.归并排序
归并排序（Merge sort）是通过归并操作达到排序目的的算法，体现了分治的思想，因为每次排序执行的操作相同，所以时间复杂度很稳定为O(nlogn)。
实现归并排序的方法有很多，其实底层思想都是将数组划分至不可再分，再将模块两两排序，直到整个数组被排序。
一种是通过回溯（递归也是一种特殊的循环，但在退出前会保存数据，因此空间复杂度较高）：
一种是非递归，直接由底至顶进行排序：
倘若给的是链表怎么办？可以通过快慢指针寻找中间节点，因为排序的时间复杂度为nlogn，所以寻找中间节点的时间复杂度在计算时可以不计，时间复杂度仍为nlogn，但是在效率上显然不如数组。
6.快速排序
大名鼎鼎的快速排序（Quick Sort）以其快速、原地排序的特点而广受欢迎。它也是基于分治策略，但与归并排序不同，快速排序的核心在于分区（partitioning），快速排序占用的空间相对较低，在特点情况下的速度高于归并排序，有很多人说Java底层采用的是快速排序，这种说法有点浅显了，Java底层的排序会根据具体场景选择最优的排序算法。
基于递归的三路划分法，遇到比key大的放右边，小的放左边，一样的放中间：
非递归的三路划分，实际上就是使用栈来模拟递归，在JVM实现中递归实际上也是创建对应的栈帧：
public static void QuickSort(int[] array) {
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(0);
stack.push(array.length - 1);
while (!stack.isEmpty()) {
int end = stack.pop(), begin = stack.pop();
// 排序
int key = array[begin], cur = begin + 1, left = begin, right = end;
while (cur <= right) {
if (array[cur] > key) {
int temp = array[cur];
array[cur] = array[right];
array[right] = temp;
--right;
} else if (array[cur] < key) {
int temp = array[cur];
array[cur] = array[left];
array[left] = temp;
++left;
} else {
++cur;
}
}
if (end > right + 1) {
stack.push(right + 1);
stack.push(end);
}
if (left - 1 > begin) {
stack.push(begin);
stack.push(left - 1);
}
}
}
值得注意的是对于快速排序，给定的数据中相同的key过多或者子区间数据有序性较高会导致时间复杂度增高,对于这两点可以采取以下优化措施：1.对于子区间的排序算法选择插排 2.对于key值的选取可以取随机数，或者找到重复度底的数。
7.堆排序
Java本身有堆的实现，这里我们为了给其他语言提供参考价值，也手动实现大顶堆。
堆是一种完全二叉树结构，基于二分的思想我们猜测堆排序时间复杂度为nlogn，看看后面是否与我们猜测的结果一致。
如何构建大顶堆，以及为什么要构建大顶堆？
大顶堆保证的是根节点的数值最大，并不能保证叶子节点是有序的，它不是二叉搜索树，所以我们通过构建大顶堆，并不断地取出堆顶的数并放到数组尾部、不断地维护大顶堆，就可以实现升序排序了。
构建大顶堆很简单，大顶堆保证根节点比叶子节点都大，我们按照这个规则不断地递归就能保证这一性质，需要注意的是给出的代码没有做int越界处理。
其中维护堆的时间复杂度为logn，循环遍历数组的时间复杂度为n，综合时间复杂度为nlogn。
8.计数排序
计数排序（Counting Sort）是一种非比较排序算法，它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。时间复杂度为n+k，其中k为待排序数组中最大的数。
9.桶排序
桶排序（Bucket sort）就是在计数排序的基础上改良的，将输入的 N 个数据均匀的分配到 K 个桶中，时间复杂度为n+k，其中k为桶的数量。
这里我们将桶划分的太细，以至于它已经成为计数排序了
10.基数排序
基数排序（Radix sort）是一种非比较型整数排序算法，这里只展示LSD的做法，时间复杂度为 O(d * n)。
public static void RadixSort(int[] array) {
int max = Integer.MIN_VALUE;
for (int i : array) max = Math.max(max, i);
List<Queue<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < 10; i++) buckets.add(new LinkedList<>());
for (int i = 0; max > 0; max = max/10, ++i) {
int radix = (int)Math.pow(10, i);
for (int a : array) buckets.get(a/radix%10).add(a);
int index = 0;
for (Queue<Integer> bucket : buckets) for (Integer a; (a = bucket.poll()) != null;) array[index++] = a;
}
}
