持续更新中。。。。。。
根据比较与否，可将排序算法大致分为比较排序和非比较排序两大类：
- 比较排序时间复杂度为O(nlogn) ~ O(n^2)，主要包括：冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序等。
- 非比较排序时间复杂度可达到线性级别，为O(n)，主要包括：计数排序、基数排序、桶排序等。
稳定性问题定义：
如果arr[i] = arr[j]，排序前arr[i]在arr[j]之前，排序后arr[i]还在arr[j]之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的数的相对顺序不变。
对于以上比较类的排序算法而言，稳定性问题是可以在定义交换函数时打破这种稳定性的。
稳定性排序算法包括：
- 冒泡排序
- 直接插入排序
- 归并排序
- 基数排序
- 计数排序
- 桶排序
比较类的排序算法中，就复杂度最优情况而言：
- 时间复杂度上：堆排序、归并排序稳定在O(nlogn)级别
- 空间复杂度上：除了归并排序和快速排序，其它排序算法稳定在O(1)级别
- 综合考虑来讲，稳定情况下归并排序的时间复杂度最优，只是空间复杂度为O(n)级别；不稳定和最坏的情况下，所有排序算法中，无论是时间还是空间上，堆排序都是最好的选择。但是堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，也就是常数因子比快速排序大，如果你需要的是“排序”，那么绝大多数场合都应该用快速排序而不是其它的O(nlogn)算法。。
原理很简单，类似于水中的一个气泡，从水底往上冒。冒泡排序就是需要进行n-1轮循环比较，每轮比较从0~n-1-i（i为次数编号）检查序列中的数，两两相邻进行比较，以升序排序为例就是：大的数往后放，这样进行完一次排序，大的数都是放在最后，直到所有次数排完也就是顺序的了。
最坏情况下需比较的次数:n(n-1)/2。
使用场景：n较小的情况。
Java代码实现：
Python代码实现：
在基本冒泡排序的基础上改进，采用两边同时冒泡的方法，也就是从左到右每次比较将大的数往后移的同时，从右到左将每次比较的最小数往前移，效率高于基本冒泡排序法。
Java代码实现：
Python代码实现：
选择排序顾名思义重在选择，那应该如何选择，每次比较选择怎样的数呢？
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
不稳定性主要表现在：
比如序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
最优时间复杂度：
即使已经是有序，还是得拿着前面的元素和后面的一个一个地进行比较，所以复杂度是O(n2)
最坏时间复杂度:
内层循环是和n有关的，复杂度是O(n2)
适用情况：n较小
Python代码实现：
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
可优化思路：
因为前一部分已经是从小到大排列的了, 所以如果从后面选出的最小元素大于前面的元素，那么就一定比前面的前面还要大，这时候就不需要进行比较了。
最优算法复杂度：
假设列表已经是从小到大排序好, 那么while循环进入一次就退出，总共进入n-1次，所以算法复杂度是O(n)。
最坏算法复杂度：
假设列表是完全无序，或者说是从大到小排列的，那么内层循环是n-1 n-2 n-3 …,和n是有关的，所以复杂度是O(n2)。
稳定性：
拿无序的第一个元素和前面的比较，比如说前面最大66，后面有一个66，因为后面的66不比前面的66大，位置不改变，所以插入排序是稳定的。
使用场景：数据量小时使用。并且大部分已经被排序。
Java代码实现：
Python代码实现：
二分插入排序是采用二分搜索法对插入排序进行改进。改进思路：在前面已经排好序的序列中找当前要插入的元素的位置时，采用二分查找的方式去找那个插入的位置(也就是大于key的那个位置) ，找到那个位置之后，再进行元素的移动，最后把那个元素插入到找到的那个位置。
Java代码实现：
Python代码：
Python代码实现：
快速排序的思想其实很简单：首先找一个基准数，一般方便直接以数组第一个数作为基准数，然后初始化两个最左和最右指针，先移动最右的指针，找到比基准数小的数就停止，然后移动最左边的指针找到比基准数大的数停止，此时交换两个指针指向的数，然后继续右指针先移动重复该过程，知道两个指针相遇，此时交换基准数和两个指针共同指向的那个数，这样就完成了第一轮的划为，以基准数为划分点，做左边的都是小于基准数的，最右边的都是大于基准数的。后续再用递归快排下左右两个部分就好了。
图解可以参考一下这篇博客：https://blog.csdn.net/shujuelin/article/details/82423852
使用场景：是最快的通用排序算法，大多数使用情况下，是最佳选择。
Java代码实现：
归并排序思路：将一个待排序的数组不断分成左右两部分进行递归排序，最后合并已排好序的即可。
归并排序也是分治法一个很好的应用，先递归到最底层，然后从下往上每次两个序列进行归并合起来，是一个由上往下分开，再由下往上合并的过程，而对于每一次合并操作，过程如下：
（1）申请一个额外的辅助数组空间，长度与原数组长度一样，用来存放合并好的序列；
（2）设置两个指针，起始位置分别为左右排好序的起始位置；
（3）比较两个指针指向的数，并将较小的数存放到合并数组中，然后继续移动指针，指针指向末尾结束；
（4）将剩余的数直接复制到合并数组的末尾。
使用场景：如果需要稳定，空间不是很重要，就选择归并排序。
Java代码实现：
- 比如最大/小的元素，topK之类。用堆排序可以在N个元素中找到top K，时间复杂度是O(N log
K)，空间复杂的是O(K)，而快速排序的空间复杂度是O(N)，也就是说，如果你要在很多元素中找很少几个top
K的元素，或者在一个巨大的数据流里找到top K，快速排序是不合适的，堆排序更省地方。 - 优先队列，需要在一组不停更新的数据中不停地找最大/小元素，快速排序也不合适。
（3）Java代码实现：
总结：
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
待更新。。。。。。
待更新。。。。。。
待更新。。。。。。