1.插入排序
插入排序的时间复杂度为O(n^2)，最坏的情况是逆序，最好的情况是走一趟就有序，也就是O(n)，
插入排序和斗地主相似，你会将牌按一定顺序排列，下面以升序为例：
我们先创建一个数组a，规定[0，end]为有序，用temp把a[end+1]的值储存起来，每次将end+1位置的数据插入进来，比较a[end+1]与a[end]的大小，如果a[end] > a[end+1]，就将a[end+1] = a[end]，end--(也就是将数据往后挪)，再比较a[end+1]与a[end]的大小，当a[end]<=a[end+1]时，a[end+1] = temp，这是单趟，总趟数是用for(int i = 0 ; i < n-1;i++)其中n是数组中的数据个数，每次将end = i,用temp把a[end+1]的值储存起来，代码如下：
这里有两个容易出错的地方，一个是for循环中i < n-1，写错会导致数组越界访问，另一个是为什么不在循环里写a[end + 1] = temp，因为有可能数组的第一个数字也要往后挪，这样会导致end = -1,直接跳出循环，不执行a[end + 1] = temp，所以写在循环外。
2.冒泡排序
冒泡排序的时间复杂度为O(n^2)，最坏情况是逆序，最好情况是走一趟后flag = 0，没有发生交换，也就是O(n),冒泡排序是两两交换，以升序为例，代码如下：
n是数组中的数据个数，第一次冒会把最大的放在最后，第二次冒会把较大的放在后面，依此类推，注意写单趟时j< n- i- 1,容易出错，因为每次都会把大的排好，假设n为5，第一次冒完后只需再排4个数，第二次冒完后只需再排3个数，依此类推，也就是n- i，再减1是因为当i=0，j=4时，a[j+1]会越界。
3.希尔排序
通过对插入排序的了解，我们知道当数据逆序时，它的效率就比较低了，这时我们就可以用希尔排序来提升效率，通俗来讲希尔排序就是对插入排序的优化，它是先对数据进行预排序(让数据接近有序，让大的数尽量在后面，小的数尽量在前面)，最后一趟用插入排序，以升序为例:
我们将数据分为三组(gap = 3)，再对这三组数据进行插入排序，如图，也就是先排蓝色线连接的，再排绿色的，最后排粉色的。蓝色排完是1,2,5,6，绿色排完是3,7,13，粉色排完是8,9,10，预排序排完是1,3,8,2,7,9,5,13,10,6。预排序代码如下:
我注释掉的部分是我上面说的思路，一组一组排，但是三层循环写得繁琐，可以写成两层循环，也就是多组同时排，蓝色的5,6排完后，排绿色的13,3，在排粉色的8,9，在排蓝色的，依此类推。不过这两种写法效率都一样。有人会说gap只能是3吗？当然不是，那gap为多少才好呢？gap越大，那么大的数越快到后面，小的数越快到前面，但越不接近有序；反之，gap越小，大的数越慢到后面，小的数越慢到前面，但越接近有序，当gap=1时，就是插入排序了。有人说gap是变化的，gap = gap/3+1，可以保证最后一次gap为1(gap到底是多少没有结论)，代码如下:
希尔排序的时间复杂度为O(n^1.3)，如果要算的话很复杂，不过我们可以粗略算一下(gap = gap/3+1，忽略掉1，gap一开始为n，所以gap = n/3)，有gap组数据，每组数据个数为n/gap，所以每组3个数据，最坏情况(逆序)，第一趟排序消耗为(1+2)*n/3 = n(每组比较次数*组数)，第二趟排序消耗为(1+2+3+...+8)*n/9 = 4n，不过第二趟是按照最坏情况计算的，其实第一趟排完后就不是完全逆序了，所以应该比4n小，具体是多少很难算，我就不展示了。最后一趟可以算，是O(n)。
如果不看内部，只看预排序的次数，就是对数次，按上面来看(省略+1)就是log以3为底的对数。
4.堆排序
想要了解堆排序首先要知道向上调整建堆和向下调整建堆，以升序为例：
我们先用向上调整建堆把它建成大堆，AdjustUp(a,1)，我们从a[1]开始调，注意while循环里面是child > 0，举个例子9要调多次，才能到对应位置。其实降序要建小堆，升序要建大堆，倘若降序建大堆的话，如图，大堆建好后，9相当于排好了不能动，后面的数字就要重新建堆，这时候你就会发现7和8本来是兄弟，重新建堆后变成父子，7和5本来是父子，重新建堆后变成兄弟，关系全部乱了，虽然这个思路也能走下去，但是建堆的代价太大，所以还是按降序建小堆，升序建大堆的思路来走。上面我们已经建好了大堆，排升序的话，我们只需将9和1换个位置，然后将9作一个伪删除(将9不看作堆中的数据)，再把堆顶的1用向下调整就可以选出次大的数(8)，接着将8和堆底的上一个位置交换，依此类推。它的效率为(O(n*logn)，每次向上调整为logn，调整n个数就是n*logn)。还有一种算法是向下调整建堆，它的效率为O(n)，比向上调整的效率高。它的思路是从倒数的第一个非叶子节点开始调，图如下(现在讨论的时间复杂度是建堆的效率):
蓝色数字是调整顺序，下面我们就来计算向下调整建堆的效率为什么是O(n)。以满二叉树为例(因为完全二叉树节点的调整次数比满二叉树少，我们以最坏情况考虑)。
因为第h层是叶子节点，不用调整，所以从第h-1层开始调，第h-1层的节点有2^(h-2)个，每个节点要最坏调整1次，第h-2层的节点有2^(h-3)个，每个节点要最坏调整2次，依此类推。就可以得到总移动次数F(h) = 2^0*(h-1)+2^1*(h-2)+...+2^(h-3)*2+2^(h-2)*1。不难看出用错位相减即可化简，F(h)= 2^h-1-h，再算一下节点个数N与高度h的关系，2^h -1 = N，h =log(N+1)(这里的log是以2为底的，不方便敲)，带入总移动次数F(n) = N-log(N+1)，约等于O(N)。我们也来看一下向上调整建堆为什么是nlogn。第一层不用调，第二层的节点有2^1个，每个节点要最坏调整1次，第三层的节点有2^2个，每个节点要最坏调整2次，第h-1层的节点有2^(h-2)个，每个节点要最坏调整h-2次，第h层的节点有2^(h-1)个，每个节点要最坏调整h-1次，依此类推。就可以得到总移动次数F(h) = 2^1*1+2^2*2+...+2^(h-2)*(h-2)+2^(h-1)*(h-1)，h =log(N+1)(同上)，化简整理得F(n) =(N+1)log(N+1)-2N，约等于nlogn。
最终堆排序的代码如图，因为是从第一个非叶子节点开始调n-1是最后一个节点，再减1除2就是第一个非叶子节点不过不管是向上调整建堆还是向下调整建堆，最后堆排序都是O(n*logn)，因为建好堆后，最后一层有N/2个节点，它们每个节点都要都要向下调整log(N-1)次，它与向上调整建堆的思路是一样的。向下调整建堆的堆排序是O(N)+O(NlogN)，向下调整建堆的堆排序是O(NlogN)+O(NlogN)，化简后总的堆排序都是O(NlogN)。
5.选择排序
选择排序就是将数组遍历一遍选出最小的数，放在左边，再选出次小的数，放在左边，也就是暴力遍历，我们做一个优化，在[begin，end]之间，遍历一遍选出最小的数和最大的数，不过它的效率不管是有序还是逆序都是O(n^2)，代码如下:
这里有个坑，就是当begin==max时，min和begin交换后，max的值会变，举个例子，a[4] = {9,4,2,8}，min和begin交换后，变为2,4,9,8，这是max就不是9了，而是2，所以要将min赋给max。
6.快速排序
快速排序有点复杂，我们先来看单趟，如图:
我们令左边第一个数为key，将左边的数给left，右边的数给right，让right往左走,找比key大的数，left往右走,找比key小的数，先找到的停一下，等另一个也找到后交换，如果一边找不到，另一边就会一直等，直到相遇，再和key交换位置，这样的话key的左边都是比key小的数，右边都是比key大的数，然后再排key的左边，再按上面的思路。这挺像二叉树的递归思想，学过的话更容易理解，代码如下:
注意一下while循环里面要加begin<end，否则begin和end相遇后就会错开，还有只有递归到一个数的时候才算有序，像上面的1和2，再递归一次就只剩1，也就是left==0，right==1，key==1，就会出现left==right和left>right，这两个就是结束条件，如上图。它的时间复杂度是O(n*logn)，因为单趟大概是在中间位置相遇，分区间的话大概也会占一半，单趟走一遍是n,递归log次(每次大概左右区间分得差不多一样)所以时间复杂度是O(n*logn)。
但是这样写有个缺点，就是数据接近有序的时候它的效率会变低因为接近有序时，右边找不到小，左边很容易找大，导致基本上右边要走N次，begin与key交换后又很靠近左边，所以第二次大概要走N-1次，依此类推，最后发现它退化成一个O(n^2)的算法了，而且递归深了容易导致栈溢出。究其问题的根本，就是选key的位置，我们希望选的key大概是个中位数，现在有两个思路：1.选随机的key 2.三数取中(选最左边，中间，和最右边的数，中间就用(left+right)/2)。当然，随机值是不可控的，我们不予采用，下面是三数取中(它大大降低了key取到最小或最大的可能性):
可能有人不理解三数取中的逻辑，我画个图就好理解了(如果会的读者可以跳过这段)。
上面的left<mid就是定了这两个的位置，让right往它们当中插入，有人可能会说为什么是先往有插，再往左插，最后往中间插，这样逻辑不是很乱吗？为什么不从右往左或者从左往右？其实不然，举个例子，如果从右往左插入的话，大前提已知left<mid，如果你写right<mid，你就不知道left与right的关系，如果你写left<right，你就不知道mid与right的关系，所以这样写是有讲究的，你也可以写成1，3，2(数字是right的插入顺序)，第二个mid<left也是同理。这样处理后，面对有序的情况，它的时间复杂度就是O(nlogn)，不会退化了。
其实到这里我们写的快速排序还有可以优化的地方，你想一想，当递归到数据很少的时候，我们还有必要继续递归下去吗？当递归到数据只有5个时，它还要走六七次递归。学过二叉树的读者知道(以满二叉树为例)，一个高度为h的树，他最后一层有2^(h-1)个节点，占了总结点数的一半(总节点有2^h-1，可以把1省略)，倒数第二层占了1/4，倒数第三层占了1/8，倒数第四层占了1/16，如果能优化最后四层，效率提升了大概90%，所以我们决定当数据量大于10时，我们走递归，剩下我们走插入排序(因为插入排序的效率实际比冒泡排序和选择排序快)，这就是小区间优化
注意是a+left，因为有左右区间，left不一定是0。
有人可能还会有疑问，为什么left和right相遇的位置一定比key小，而且必须让right先走(如果比key大那就没有做到比key小的在它左边，比key大的在它右边)，首先相遇有两种情况：1.left遇right，2.right遇left。left遇right：right先走，先停下来，停下来的地方一定是比key小(因为right找小)，left没找到大的就与right相遇了；right遇left：right先走，没找到比key小的，就和left相遇了，left停下的地方是上一轮交换完了的位置，所以也比key小(有人会问为什么right不能在比key大的地方停下，right一直往左走直到相遇？因为我们是让right先走，所以只有当right停下时left才能走，而当right停下也就是遇到了比它小的值，left也停下，那么就要交换了，而right要是不停下，最差也是在key的地方相遇，然后key和自己交换)。当然非要右边先走也行，只需将key挪到右边，而不是左边。
还有一种排单趟的方法：挖坑法，就是先把key(我默认在左边)的值放在一个临时对象里，这就形成了一个坑，再让右边先走找小，找到后放在坑里，这样又形成了一个坑，然后让左边走找大，找到后放到坑里，依此类推，最后left和right会在坑相遇，这样写就不用考虑为什么右边先走(因为左边挖了坑，要让右边填上)，也不用考虑为什么相遇的位置比key小(因为在坑相遇不用考虑)，还不需要用交换，代码如下:
还有一种是前后指针法，令prev = left，cur = prev+1，当cur<= key时，我们就把prev++，然后交换a[prev]和a[cur]，再cur++，为了防止自己与自己交换，prev++ != cur。当cur> key时，cur++。最后交换a[key]和a[prev]的值。代码如下:
小结一下，我们现在看了三种单趟的方法:1.hoare法(也就是)，2.挖坑法，3.前后指针法，不过它们三个的效率都是O(n)。
不过，递归有栈溢出的风险，我们可以尝试写非递归，这时候就要借助栈或队列，栈的“后进先出”模拟递归很像(像深度优先遍历)，所以我们来用栈模拟实现非递归，代码如下：
这里我就不展示栈的增删查改了，我们来看一下它的逻辑：就是用下标来控制区间，不是将数组里的数据往里面入，它入就是入begin和end两个下标，排序就是Quicksort3来控制，我画一张图来解释一下:
箭头的意思是出栈顺序，先入9(因为栈是后进先出，所以先入9，后面同理)，出9，再入0，出0，key为5，入9，入6，入4，入0，再出0，出4，依此类推。
7.归并排序
归并排序用的也是递归思想，我们先看代码:
它的核心是在第二个函数，第一个函数开一个额外数组，第二个函数也是要用下标分割空间，当递归到只有一个数时，才算有序，我画一个图方便理解:
它是先走0~9，0~4，0~1，0~0，再走1~1，2~2，3~4，右半部分逻辑一样，我就不画了。它有点像二叉树的后序遍历。最后把数排好后再拷贝回原来的数组。它的时间复杂度是O(nlogn)，层数是logn层，每层处理n个数，所以是nlogn，它的空间复杂度是O(n)，因为开了一个额外数组。
我们再写一下非递归，如果用栈来存放的话，需要开两个栈，所以我们用循环来写，代码如下:
写非递归要注意边界，它的思路相当于是从递归的最后一层开始，如图，[0,0][1,1]...，gap是先一一归并，再二二归并，再四四归并...，这是gap的作用，但是这样写有越界风险，换一组数据，如图:
这一组数据有十个数，后三排都有越界，由图可知begin1不越界，end1，begin2，end2有可能越界，当end1越界时，其他两个一定越界，当begin2越界时，end2一定越界，所以分两种情况，begin2是否越界，end2是否越界(有人可能会问为什么不管end1，看图[8，11]就是end1越界情况，这时[8，11]有效数据只有下标8，9，又因为8，9在上面已经排好，所以直接break即可，不管end1，是否越界，只要begin2越界，就要这么处理)，end2越界只需将end2改为n-1即可。
8.计数排序
计数排序的逻辑是统计数据出现的次数，我们先看代码:
它首先选出数组中的最小值和最大值，作差后就可以选出它的范围，进而确定开多大的空间(有人可能感到疑惑，要是有重复的数据，空间不就开小了吗？)，其实我们开的这个temp数组只是为了统计数据出现次数，最后再覆盖原数组。
但是如果排的数据从100~109，难道要开109个空间吗？当然不用，我们可以将100看成0，109看成9，即相对映射，也就是a[i]-min，不过记得最后i+min，把数据还原。它的时间复杂度是O(n+range)，要是n与range差不多大，那么即为O(n)，效率很高，但缺点也很明显，就是只适合排数据比较集中的，数据是整数。
9.基数排序
它的核心思想就是按百位，十位，个位这种位数来排，它是先排个位再排十位再排百位，依此类推，但是有了计数排序，它就显得很鸡肋了，因为它不能排负数，计数排序可以，它只适合都是百位数或者都是十位数等等，而且计数排序的缺点它也有：只适合排数据比较集中的，数据是整数。我们只了解就行了。
10.桶排序
它的核心思想就是创建一个指针数组，但是数组的下标永远都是0~9，而且最高位是几就挂几号桶，后面是用链表连接，连到链表的数据还要排序，可以走一个插入排序，它只适合数据比较均匀，如果不均匀，比如都在一个桶就没意义了。
总结
我们把重要的七大排序总结一下，首先把稳定性的定义说一下：值相等的两个元素，排序完成之后，它们原来的先后顺序保持不变。举个例子[1，2(a)，2(b)]，这是排完前的顺序，稳定排序排完[1，2(a)，2(b)]，a还在b的前面，不稳定排序排完[1，2(b)，2(a)]，a,b的位置颠倒了。
稳定排序我就不解释了，我们看为什么其他几个排序为什么不稳定，希尔排序(相同的数分到不同的组，无法控制)，堆排序(如果是[2，2，1]，建堆再排序后，堆顶的数与堆底交换，第一个2就跑后面去了)，选择排序([2，2，1]，把最小的1与2交换后，第一个2就跑后面去了)，快速排序(分组也无法控制)，最后归并排序的空间复杂度为O(n+logn)，递归与temp都要开空间，只不过将logn省略了。其实我们可以发现涉及交换的排序大多是不稳定的。
感谢大家的阅读。
