归并排序（稳定的 N＊lgN）

外排序（超出了内存范围）

    如何用1G内存对10G数据进行排序？

        读入1G数据到内存，用常规排序算法进行内排序，

        将排序后的数据写入磁盘，

        重复上面的过程相当于对10G数据分成10分，分别进行内排序，产生10个排序文件，

        分别将10个文件的前100M数据读取到内存公1G进行排序后写入最终的结果文件，

        依次读取文件后面的数据，排序后追加到结果文件即可。

    求数组中的逆序对或个数？

 

    杨氏矩阵（矩阵每行和每列都是有序的）是一个MN的二维数组

        对杨氏矩阵做插入的方法是，将待插入数据与最大的数据进行比较，（矩阵中最大的数据是在角上）

        如果待插入数据比它小，再与横向和纵向移动进行比较，类似冒泡方式，逐渐找到应该在的位置

 

非比较方案的排序：    计数排序／桶排序／基数排序

常见的七种排序算法解析

http://mp.weixin.qq.com/s/XD0T4zgLr58E3mPmGB_tpA

 

秒懂排序算法 

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。

在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。 比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

 

计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

https://mp.weixin.qq.com/s/t0dsJeN397wO41pwBWPeTg

 

堆排序：

1.完全二叉树，一个结点i它的左孩子是2*i+1，右孩子是2*i+2

2.最后一层的最后一个叶子结点的父结点为 （lastIndex-1）／2

因此先实现创建最大堆方法。

    从最后一层的最后一个叶子结点的父结点开始循环往回计算，这样可以遍历所有的子结点和父结点的关系。在每个结点处理过程中将子结点的值（最多两个）与父结点的值比较找出最大的，将其放在父结点，即最大堆的特点是，任何一个结点都比它的下面的节点值要大。注意如果父结点的值比子结点的值小进行交换，交换后可能打破下面的最大堆关系，所以交换后要继续处理一遍子树，保证它依旧符合最大堆条件。

最大堆创建完成后，根结点为这颗树的最大元素，因此将跟结点和最后一位交换，即最大值沉淀。然后将数组缩小一位，继续创建最大堆，交换根结点与当前这个数组（比上面小一位）最后一位交换（最大值沉淀），因此最外层就是循环沉淀每一次的最大堆里的最大值。

https://www.cnblogs.com/CherishFX/p/4643940.html

https://blog.csdn.net/jianyuerensheng/article/details/51263453