排序算法总结

最近在复习排序算法的知识，写下来加强记忆。

1. 冒泡排序

这好像是被认为最基本最简单的排序方法。为什么叫冒泡呢？因为按照这种排序方法，最小值会像一个气泡一样一点点的浮上来。既然是一点点浮上来，其实就说明这个方法是会进行逐一相邻元素的比较。算法的具体思路是：首先排第一个元素，也就是找最小的元素，方法是从最后两个元素开始比较，如果后一个元素比前一个元素大，则交换，否则用前一个元素跟他的再前一个元素比较，重复这样的过程，最后最小的元素就会到第一个位置了。然后再确定第二个位置，依此类推...显然，这样的复杂度是o（n2）。而改进的话可以这样考虑，假设数组一开始就是有序的，那么一次遍历后就没有交换，在这种情况下，可以直接判断数组有序，无需再遍历。这样可以把最高的情况提高到o（n）

2.选择排序

为什么叫选择排序呢？因为整个排序的过程实际上就是在不断选择最小值的过程，其具体思路是：也是先要确定最小的元素，也是要比较，但不是每次比较之后都交换，而是要找到最小的值之后再交换，每一次比较，较小的那个值就命名为min，以一个元素为标准，遍历一遍之后，就能够找到最小的值，把它放到第一位，然后再对其他的值做同样的操作，找到第二小的，放到第二位，依此类推...显然，这样的复杂度也是o（n2），而且无论最坏还是最好都是o（n2），因为我每次遍历都是和同一个值进行比较，因此没有办法可以剪枝。但是选择排序有一个优点，就是它的一移动次数比较少。

3. 直接插入排序

为什么叫插入排序呢？因为并不是每次比较后就会执行交换操作，而是发现某一个合适的位置后就把这个数插入进去（当然其他的值也要做相应的调整）。具体思路是：从第二个数开始，每个数和它前面的数比较，如果前面的数大，前面的数就往后移一位（似乎可以看成是一个恶霸，看见谁好欺负就往后推，这样每次它前面都会空出一个位置），直到碰见比它小的，就插入空位。这样呢，最好的情况，显然是数组完全有序，那就完全不用挪窝，复杂度o（n），最坏的情况，完全倒序，最厉害的人在最后，那就是o（n2）

4.希尔排序

希尔排序是插入排序的升级版。插入排序最好的应用场景是数据基本有序（也有说数据量较小的时候，是不是数据量小的时候基本有序的概率比较大？）。但是现实当中的数据很多都是乱序的，如果保证基本有序呢？混乱之中有时也蕴藏着一些规律，如果我们能够把这些规律发掘出来，是不是就可以了？如何发掘？全部数据是乱序的，但是我是不是有可能挑选一些数据就是基本有序的？于是想到每隔一段距离选一个数，这样组成一个基本有序的序列，然后不断缩小距离，直到距离为1时，全部序列应该都是基本有序了，这时候再做一次直接插入排序，就可以了。希尔排序的最好情况时间复杂度o（n1.3），最坏o（n2）。

5.堆排序

堆排序是怎么想到呢？实在不知道，因为实在不像是常人能够一下子想到的一个东西。所以也就直接介绍思路了吧。具体思路是：我先把乱序的数组变成一个稍微有序的结构，叫做堆。首先第一个数是最大的，接着两个数是第二层，接着四个数是第三层...如何构建这样的结构，我觉得很关键的一点是要了解，如果把一个数组构建像上述那样构建为一个二叉树，那么它最大的带有子树的结点的下标应该是数组长度除以2并向下取整，这样其实就把元素调整的范围缩小了。剩下的就是从这个结点开始往上进行调整，把最大的调整到顶端之后再和最后元素进行交换，再调整...堆排序的时间复杂度无论最好最坏还是平均都是o（nlogn），这也是比较好的一点。但因为有交换，所以不稳定。

6.归并排序

归并排序的思路似乎更直接一点：先排小元胞，再把他们并在一起。递归方法的话就是不断二分，当只有一个元素的时候就直接相等；非递归就是分到最小然后一对一对的遍历。归并的最好最快最差也都是o（nlogn），但是因为并的过程需要一个新的数组，所以空间复杂度要高一点。但是是稳定的

7.快速排序

快速排序应该是目前实践中最常用的方法。它之所以快主要是它的常数项系数比较小。它的基本思路是：选定一个pivot，然后把比他小的都放到一边，比他大的都放到一边，然后再递归。快速排序的时间复杂度平均和最好都是o（nlogn），最坏是o（n2），最坏的情况应该是每次选到的pivot都偏小或偏大的时候。