排序算法
排序算法算是我们学习算法的入门篇，在正式介绍各种排序算法前，先介绍一下要用到的一些术语：
稳定排序：如果a本来在b的前面，且a==b，排序以后a依旧在b的前面，那就是稳定排序，否在是非稳定排序
原地排序：就是在排序过程中不申请多于的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。而非原地排序就是需要利用额外的数组来辅助排序。
总览：
首先找到数组中最小的元素，其次将其与数组中第一个元素交换位置，然后在剩下的数组中找到最小的元素，然后和第二个元素交换，以此类推，直到交换完毕。
数据移动最少，运行时间与数据输入时的顺序无关
时间复杂度：O(n²)
空间复杂度：O(1)
非稳定排序
原地排序
数据量少
像抓牌一样，将牌暂时放入现在的适当的位置。当到最后一个元素时就排序完成了。就像把一个无序数组中的数据整合到一个有序数组中。
运行时间与输入情况有关，对于一个部分有序（数组中元素离最终位置都不远，或者一个有序的大数组加一个小数组）来说速度比较快
稳定排序
数组基本有序，或者一个有序的大数组中添加一些小数据。
十分简单，重复访问，依次比较进行交换，交换过多
比较相邻元素，大就交换
从第一对开始，到最后一对，一次排序后保证最大的位于末尾
重复n次
思路简单
时间复杂度：O(n2)
无适用场景一般用于学习算法。
改良冒泡排序算法 在我们遍历的过程中，会发现从开始第一队到最后一对都没有发生交换，此时意味着，剩下这些待排序的元素已经是有序的数据，无序再次排序，所以我们可以引入一个标志，当遇到此情况的时候，直接跳出循环。减少无意义的比较和缩短排序时间。
希尔排序是插入排序的一种变种，原来插入排序的优势在于数据基本有序的情况下性能很好，但是如果原数组中的元素距离其正确位置很远的话，效率就不是很高，而希尔排序正是优化了这一点。
希尔排序就是为了加快速度简单的改进了插入排序，交换不相邻的元素以对数据的局部进行排序。
先使数组中任意间隔为h的元素是有序的。最后对于一个以1结尾的的h序列我们都能够将其排序。
具体步骤：
先将整个待排序的记录序列分隔成若干子序列，分别进行直接插入排序
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
基于插入排序的快速排序
时间复杂度：O(nlogn)
大型数组，大多数情况下希尔排序都是比较高效且简单的算法
需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再对另一个组排序，而是轮流对每个组进行排序。
将一个大的无序数组有序，我们可以利用归并的思想来进行排序，即将大问题化为小问题进行解决。
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
速度较快，不受输入数据的影响，所需额外空间与N成正比
空间复杂度：O(n)
非原地排序
我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。
应用广泛，原地排序，几乎不需要额外的空间
空间复杂度：O(logn)
广泛
利用堆这种数据结构，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。
基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
时间复杂度：O(n+k)
空间复杂度：O(n+k)
其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
针对计数排序进行优化的一种算法。
时间复杂度：O(kn)
代码思路倒是很简单，就是利用线程睡眠来进行排序，让线程睡眠、
娱乐算法，没啥特点就是好玩
就是让系统随机排序，然后验证是否有序
巨复杂，看命
如果觉得看完有收获，希望能给我点个赞，这将会是我更新的最大动力，感谢各位的支持
欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我
如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。
——我是冢狐，和你一样热爱编程。
