当待排序数据中有相等的元素, 并且排序后相等的元素次序没有改变, 就说这个排序是稳定的.
冒泡排序 插入排序 归并排序 基数排序
选择排序 快速排序 希尔排序 堆排序
冒泡排序 O(n^2) 选择排序 O(n^2) 插入排序 O(n^2) 希尔排序 O(n^1.5) 快速排序 O(NlogN) 归并排序 O(NlogN) 堆排序 O(N*logN) 基数排序 O(d(n+r))
基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
过程：
1. 比较相邻的两个数据，如果第二个数小，就交换位置。
2. 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，
这样第一个最小数的位置就排好了。
3. 添加flag标志位, 当前有无交换, 如果无交换, 证明已经排好.
4. 继续重复上述过程，依次将第2.3…n-1个最小数排好位置。
基本思想：每次选择最小的数, 然后与前面交换 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换； 第二次遍历n-2个数，找到最小的数值与第二个元素交换； 。。。 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
基本思想: 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的
有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
过程:
1. 从下标1开始, 与下标0比较, 如果小就交换
2. 再从下标2开始, 依次往前面比较
注: 数据序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1; 数据序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3; 如果数据序列基本有序，使用插入排序会更加高效。
基本思想： 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
过程: 1. 取一个增量i(len / 2), 然后使用增量做为比较数之间的间隔, 然后进行插入排序 2. i /= 2, 继续步骤1
基本思想：（分治） * 先从数列中取出一个数作为key值； * 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边； * 对左右两个小数列重复第二步，直至各区间只有1个数。
基本思想：
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数
，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较
，如果有数列为空，那直接将另一个数列的数据依次取出即可。
//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成2组A，B
，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？
可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时
，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了
。这样通过先递归的分解数列，再合并数列就完成了归并排序。
基本思想:
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏
，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值
，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点
。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆
，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
步骤:
1. 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)
2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换
，得到第二大元素。如此反复进行交换、重建、交换。
基本思想:
BinSort想法非常简单，首先创建数组A[MaxValue]；然后将每个数放到相应的位置上
（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。
RadixSort: 基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销.
双层桶 Bitmap 多路归并排序 两两归并排序