下面比较几种基础的排序算法
首先：没有一种基于比较的排序算法可以在log(n!)~n·log(n)时间内完成n个元素的排序。但是排序算法中有一些特别的例子，并不是基于比较，但是时间复杂度确实以线性进行的，比如基数排序。
其次：算法的稳定性是指，当序列中存在相等的数据时，在排序过程中，如果相等数据的相对位置保持不变，那么这个排序算法就是稳定的。
这里讲述的算法有：
插入排序：直接插入、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：直接排序、堆排序
归并排序
1，直接插入排序。
插入排序由n-1趟排序排序组成，每一趟当中，第i（i>0)个元素都要和前面i-1个元素依次做比较，经过swap逐个交换找到对应的位置。
最好的情况是这个序列本身就是排好序的，那么它比较的次数就是n-1，移动的次数就是2(n-1)——中间有temp存储。时间复杂度O(n)。
最坏的情况是这个序列是倒序的，那么key[i] 的每一趟比较都要进行i次并且移动i+2次，总共的比较次数累加起来就是n(n-1)/2，移动的次数是(n+4)(n-1)/2.时间复杂度是O(n^2)。
平均情况，我们取折中的方式，每一趟比较的次数是(i+1)/2，移动的次数是i/2+2，时间复杂度O(n^2).
空间复杂度：O(1)
算法稳定性：插入排序算法是稳定的。
2，折半插入排序
折半插入排序是在直接插入排序上面做了一点点改进，在比较过程中，只比较lowest，medium，highest三个位置的元素，然后调整指针找到合适的位置。因此折半插入排序的时间复杂度依然是O(n^2)。空间复杂度：O(1)。
3，希尔排序（缩减增量排序)
希尔排序进行的是分组插入排序。分组的方式通常是，分组数是折半取整。增量是指每组相隔的距离，等于组数。组内进行直接插入排序，然后重新折半取整分组、排序。直到增量变为1，进行一次整组数据的直接插入排序，保证排序完成。
由上文我们知道，数据越接近有序，直接插入排序的效率越高。希尔排序分组以后组内的n很小，排序速度比较快，而且随着排序的进行，组内越来越有序了，排序效率也高了。这样一来，希尔排序把N^2的时间复杂度变成了很多个n1^2,n2^2,n3^2……（n1+n2+n3+……=N)加和的时间复杂度了，效率得到提高。但是希尔排序也可能有重复排序的缺点。
最好的情况当然还是排好序的，对时间复杂度的分析考虑，则取决于分组和排序的次数。
最坏的情况分析起来就很复杂了，希尔排序的时间复杂度依赖于增量的选择，而关于增量的选择，读者可以了解一些Hibbard和Sedgewick增量。（其实小编还没全弄明白。。）。
空间复杂度：O(1)。
算法稳定性：因为希尔排序是跳跃式排序的，无法保证相等元素的相对位置保持不变，是不稳定的。
4，冒泡排序
冒泡排序，顾名思义，就是把最大的泡泡冒出来，或者让小泡泡沉下去。以升序举例，要对n-1 个数据进行冒泡操作，冒泡操作就是从头开始两两比较，把较大的数据交换到后面，即第一个和第二个比完，就让第二个和第三个比，依此类推。让最大的数字移到了最后，第二大的数字在倒数第二……，
在算法实现的过程中，如果冒泡过程没有元素发生交换，则说明这个序列是排好顺序的，因此还需要加入一个判断元素是否排好序的标志。
最好的情况，就是排好序了，只要比较一轮，时间复杂度O(n).
最坏的情况，倒序，要比较n-1轮，每轮交换3(n-i-1)次，时间复杂度是O(n^2).
空间复杂度：O(1).
算法稳定性：逐个比较，稳定。
5，快速排序
快速排序，形象地说就是挖坑和填坑的过程。快速排序也是分治的递归算法。
这里涉及到两个步骤，一个步骤是partition——使得对于某个数字，使得序列左边都比它小，右边都比它大。第二个步骤就是递归，对于基准的左边和右边不断进行partition。
partition描述：首先我们选取序列中的一个值values[0] 作为基准，该值所在的位置(i=0)成为一个坑，通常是第一个数字，然后从最右边开始向右扫描，找到第一个比基准小的数字values[h]，把这个数字挖掉，填到坑里，即values[0] =values[h]。然后从新坑的最左边开始向左扫描，找到第一个比基准大的数字values[l]，继续进行挖坑和填坑的操作，把这个数字挖掉，填到坑里，即values[h] =values[l]。直到h和l相遇，把基准值填到坑里，此时基准左边的数字都比基准小，右边都比基准大。
时间复杂度取决于partition算法的时间复杂度(O(N))和递归调用的次数。如果每次进行partition算法，都能将左右子序列分成长度相等的两块，即每次选择基准的时候都能选到中位数的话，那么这就是最好的情况了，只要执行log(n)次，就能完成排序。最好的情况时间复杂度是O(n·log(n))。
但是如果每次得到的左右子序列的长度差都是n-1，即每次选取到的基准都是极值，那么要执行n次partition才能完成排序。最坏的情况下时间复杂度是O(n^2)。
空间复杂度：因为使用了栈空间来实现递归，所以最好和最坏的空间复杂度分别是O(log(n))和O(n)。
算法稳定性：因为数据两两之间的比较和移动是跳跃的，所以不稳定。
小结：当数据量小、较为有序或者基准选取不合适的时候，快速排序的效率比较慢，但是对于数据量较大且排列无序的时候，快速排序的效率是很高的。
6，直接排序
直接排序的算法思想是每次依次从序列中找出最小，交换到第一位，找出次小的交换到第二位，以此类推。因为要对n-1个元素逐个进行n-i次比较，所以时间复杂度是O(n^2).
空间复杂度是O(1).
算法稳定性：不稳定。
7，堆排序
堆的定义：对于有n个元素的序列(从0开始），始终保证第[i]个元素比第[2i+1]和[2i+2]个元素都大或都小，大即大堆，小即小堆。但是第[2i+1]和[2i+2]个元素之间无规定的大小关系。堆是一种特殊的完全二叉树，其父母结点大于等于/小于等于孩子结点。
堆排序的算法思想就是，把这个序列构造成一棵完全二叉树，把二叉树改造成堆，通过根节点获得最大或最小值后，把根节点和尾结点进行替换，删除尾结点。 然后不断重复上面改造堆和的过程。不断地找到最大和最小值。
建堆的方式是从最后一个父亲结点开始，对每一个父亲结点进行 沿较大或较小孩子向下调整的操作。第一轮建堆完成后，剩下的建堆过程只要从对根结点进行沿着较大或较小孩子的调整操作就可以了。
时间复杂度分析：建堆的过程时间复杂度是O(n)，建堆一次。调整堆过程的时间复杂度是O(log n)，调整n次。所以堆排序的时间复杂度是O(n·log n)。
空间复杂度：O(1)
算法稳定性：不稳定。
8，归并排序
归并算法就是将由n个长度组成的序列划分成n个长度为1的子序列，然后两两进行归并，再两两归并，直到归并成长度为n的序列。这里涉及到的操作有，对所有子序列两两进行merge()操作，然后让子序列长度加倍。
时间复杂度：归并排序可以看作是一个递归的过程，merge()的时间复杂度是线性的，归并排序的时间是递归排序的时间加上merge的时间。或者看做分割的趟数(log n)和 每一趟比较的次数(n/2)及移动的次数(n)加和 的乘积。归并排序的时间复杂度是O(n·log n)。
空间复杂度：不使用递归的归并排序空间复杂度是O(1)。
算法稳定性：两两比较，稳定。