数据结构
排序
冒泡排序
【转】https://www.cnblogs.com/shen-hua/p/5422676.html
前后比较，每趟选取一个最大值，每趟比上一次少比较一次。最好的情况是正序时间复杂度O(n)，最坏的情况是逆序，时间复杂度是O(n^2)。 因此冒泡排序的时间复杂度为O(n^2)。
只需要一个辅助空间，稳定的排序算法。
改进：增加一个exchange 看是否发生交换，如果没有交换那么就排序结束。
选择排序
转https://blog.csdn.net/jsjwr/article/details/79638883
简单选择排序：
每次选取出一个最小的数。
当待排序数组为正序时，移动次数为0，逆序时，移动次数为3（n-1）。
总的比较次数为 （从i=1到 i=n-1） ∑（n-i）=n（n-1）/2=O(n^2)；
时间复杂度为O(n^2)， 不稳定。
堆排序
【转】https://www.cnblogs.com/chengxiao/p/6129630.html
堆的定义：堆是具有下列性质的完全二叉树：每个结点的值都小于（小顶堆）或大于（大顶堆）其左右结点。
堆排序是简单选择排序的改进，把每次比较的结果记录下来。
堆排序的时间主要是用在构建堆以及重建堆时的反复筛选，初始建堆需要O(n)， 堆排序的时间复杂度为O(nlog2n）。
堆排序对于初始的数组排列顺序不敏感 。不稳定。
插入排序
思想:将待排序表看作是左右两部分，左边有序，右边无序。然后将右侧的无序插入到左侧的有序。
直接插入排序
【转】https://www.cnblogs.com/skywang12345/p/3596881.html
找到合适的插入位置，然后往后移动。
最好的情况下，正序，移动的次数为2（n-1），时间复杂度为O(n）。
最坏的情况下，逆序，比较的总次数为n（n-1）/2，移动的总次数为（n+4）（n-1）/4，时间复杂度为O(n^2）。
时间复杂度为O(n^2)
稳定，当待排序序列基本有序时或者待排序记录较少时，最合适。
希尔排序
是对直接插入排序的一种改进
【转】https://www.cnblogs.com/skywang12345/p/3597597.html
跳跃式的插入排序。
时间复杂度在O(n^2)与O(nlog n）之间 。不稳定。
快速排序
【转】https://blog.csdn.net/code_AC/article/details/74158681
选取一个基准值（一般选择第一个元素）。然后将比关键字小的放到前面，比基准值大的放到后面。两个指针 i，j。一前一后，当i =j时停止。
时间复杂度O(nlogn) 不稳定。
最好情况时选取的数字为中位数，左右两边相等。最坏的情况是基准值为极值。
归并排序
转https://www.cnblogs.com/skywang12345/p/3602369.html
时间复杂度为O(nlogn)最好，最坏，平均。
空间复杂度O(n) 不稳定。
原文：https://www.cnblogs.com/needoffer/p/10808766.html