最好o(n)，最坏时间o(n^2)，较稳定
基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
时间复杂度：o(n*log(n))，不稳定
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
直接插入排序的的步长是为1的，而希尔排序向前比较是以一定步长向前比较。
最好：o(n^2)，最坏：o(n^2)，不稳定
基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
最好：nlog(n)，最坏：nlog(n)，不稳定
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
初建堆：
将一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而可以反复利用上述调整的算法，自底向上逐层把所有子树调整为堆，直到整个完全二叉树为堆。最后一个非叶节点位于n/2(向下取整)个位置，n为二叉树结点数目，因此，筛选从n/2(向下取整)个结点开始，逐层向上倒退，知道根节点。
调整堆：
这是为了保持堆的特性而做的一个操作。对某一个节点为根的子树做堆调整，其实就是将该根节点进行“下沉”操作(具体是通过和子节点交换完成的)，一直下沉到合适的位置，使得刚才的子树满足堆的性质。
在对应的数组元素a[i], 左孩子a[left(i)], 和右孩子a[right(i)]中找到最大的那一个，将其下标存储在largest中。
如果a[i]已经就是最大的元素，则程序直接结束。
否则，i的某个子结点为最大的元素，将a[largest]与a[i]交换。
再从交换的子节点开始，重复1,2,3步，直至叶子节点，算完成一次堆调整。
这里需要提一下的是，一般做一次堆调整的时间复杂度为log(n)。
堆排序：
数组储存成堆的形式之后，第一次将a[0]与a[n - 1]交换，再对a[0…n-2]重新恢复堆。第二次将a[0]与a[n-2]交换，再对a[0…n-3]重新恢复堆，重复这样的操作直到a[0]与a[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。
view code
o(n^2)，稳定
基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
双向冒泡排序算法步骤
比较相邻两个元素的大小。如果前一个元素比后一个元素大，则两元素位置交换
对数组中所有元素的组合进行第1步的比较
奇数趟时从左向右进行比较和交换
偶数趟时从右向左进行比较和交换、
当从左端开始遍历的指针与从右端开始遍历的指针相遇时，排序结束
最好：o(nlog(n))，最坏：o(n^2)，不稳定
基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
假设待划分的序列为a[left]，a[left+1]......a[right]，首先将基准记录a[left]移致变量x中，使a[left]相当于空单元，然后反复进行如下两个扫描过程，知道left和right相遇。
1.left从右向左扫描，直到a[right]<x，将a[right]移至空单元a[left]中，此时a[right]相当于空单元
2.left从左向右扫描，直到a[left]>x，将a[left]移到空单元a[right]，此时a[left]相当于空单元。
当left和right相遇时，a[left]或a[right]相当于空单元，且a[left]左边均比它小，右边均比它大，最后将基准记录移至a[left]中，完成了一次划分，再对a[left]的左子表和右子表进行同样的划分。
三路快排
在排序过程中分为比基准元素小的部分：[left,lt]，等于基准元素的部分：[lt+1,i)，大于基准元素的部分：[gt,r]
单链表快排
slow指针及左边的元素都小于基准元素，fast指针用来遍历，当遇到比基准元素小的时候先slow后移，此时slow指向的肯定比基准元素大，在交换slow和fast指向的元素的值，相当于slow向右扩充。
最好：o(nlog(n))，最坏：o(nlog(n))，稳定
算法思想：
假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（向上取整）个长度为的有序子序列，在此基础上，在对长度为2的有序子序列进行两两归并，得到若干个长度为4的子序列，重复，知道得到长度为n的有序序列为止。
tmp存放在归并时完成归并的数组，然后再将其赋值给原数组。
单链表归并
平均时间复杂度：o(n)，最好：o(n)，最坏：o(n)，稳定
基本思想：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
整个算法过程描述如下：
1、将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
2、从最低位开始，依次进行一次排序。
3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的时间复杂度是 o(k•n)，其中n是排序元素个数，k是数字位数。
平均时间复杂度：o(n)，最好：o(n)，最坏：o(n)，不稳定
算法描述和分析
设置一个定量的数组当作空桶子。
寻访串行，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的串行中。
算法简介
计数排序(counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组c，其中第i个元素是待排序数组a中值等于i+min的元素的个数。然后根据数组c来将a中的元素排到正确的位置。它只能对整数进行排序。
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组c的第i项
对所有的计数累加（从c中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第c(i)项，每放一个元素就将c(i)减去1
计数排序是一种以空间换时间的排序算法，并且只适用于待排序列中所有的数较为集中时，比如一组序列中的数据为0 1 2 3 4 999;就得开辟1000个辅助空间。
1.将待查找关键字k与索引表中的关键字进行比较，已确定待查找记录所在的块，可用折半查找或顺序查找
2.进一步用顺序查找，在相应的块内查找关键字为k的元素。