排序算法总结
排序是算法问题中的经典问题。为什么要总结排序算法呢？你懂的 : (
假设所有的排序都是要求最终结果为：从小到大
冒泡排序
时间复杂度O(n^2)、最好是O(n)。空间复杂度O(1)、稳定排序。
冒泡排序，输入一个长度为n的数组，遍历这个数组最多n次。
从最后一个元素开始，依次比较: (n,n-1), (n-1,n-2) , (n-2, n-3) ..... (3,2),(2,1)。
其中括号中的两个数字表示元素下标（这里从1到n），即相邻元素进行比较：
- 如果比较 ( i , i-1 )时， 第 i-1 个元素比第 i 个元素大，立刻交换这两个元素
- 否则， 继续比较(i-1.i-2)
这样一次遍历到此结束，它起到的效果是，每次一个最小的元素将冒泡到前面。
举个例子: {3,2,5,1,4}，开始第一次遍历：
- 比较(1,4)，1<4，继续比较(5,1)
- 5>1, 所以交换。现在数组是{3,2,1,5,4}
- 接下来，比较(2,1),由于2>1，交换。交换后比较的是(3,1)
- 最终的数组为{1,3,2,5,4}, 最小的1被冒泡到最前面。
- 继续对该数组作剩下最多n-1次遍历。
为什么是n-1呢？
优化1：因为冒泡排序其实可以做一些小小的优化，比如一次遍历，如果没有发生交换，那么其实数组已经排序好了，可以直接return.
优化2：因为每次迭代，都会把剩下的最下的放在前面，那么第 i 次迭代的时候，其实没必要和最前面的i-1个数组进行比较，因为前面i-1的位置不能再被动摇了. 这样会减少一些比较的次数。
选择排序
时间复杂度O(n^2)、空间复杂度O(1)、不稳定排序。
选择排序，输入一个长度为n的数组，遍历这个数组n次（标号为0,1,2...n-1次遍历）。对于第 i 次遍历：要实现一个目的，确定第i小的元素是谁，将它放入array[i]的位置。 比如第0次遍历，确定最小的，放入array[0]，之后是array[1],array[2]....array[n-1].
具体过程是：每一次遍历，都要遍历一遍数组，找出剩下的元素中最小的，记录下标，最后和当前元素交换。
实际上，选择排序和冒泡排序是类似的，都是每次迭代的结果是确认一个最小的。但是选择排序好就好在减少了swap的次数，可以说是冒泡排序的升级版本。
插入排序
时间复杂度O(n^2)、最好是O(n)、空间复杂度O(1)、稳定排序。
插入排序是一个整牌的过程。废话不多说，加入发完牌后，你手里有：
5，2，3，1，4
这时候你开始整理牌，你从第二张牌开始，发现前面的5比2大，你就把2插入到了5的前面（通过交换完成）。现在:
2，5，3，1，4
现在你看3，发现5比3大，把3插入到5前面（通过交换完成），然后继续比较3和2，然后3不能插入到2的前面。现在:
2，3，5，1，4
现在看1，与5比较，插入到5前面（通过交换完成），然后继续与3，2比较，一直交换到最前面。现在：
1，2，3，5，4。最后一步不多说了：1，2，3，4，5。
唯一的不同是插入是一步一步的，必须通过交换一步一步的来。愿因是数组元素不能一次性插入到好几个元素前面。
快速排序
时间复杂度O(nlogn)、最坏情况O(n^2)。空间复杂度O(1)、不稳定排序。
快速排序是考察最多也是应用最多的排序算法了。因为它的思想可以使用到其它很多地方，比如第k大元素等问题。
快速排序最重要的是划分的思想。 划分将数组中某一个元素，左边都比这个元素小，右边都比这个元素大，也就是说，划分之后，元素一定处于最后排好序的位置。
经过划分，我们就可以使用分治的思想解决问题，因为划分之后，一个元素位置已经确定，所以只需要分别递归的解决元素左边和右边的数组就可以了。
归并排序
时间复杂度O(nlogn)， 稳定排序。
归并排序是分治法非常经典的体现。归并排序首先找到了数组的一个中间界限，并分别解决左边的排序和右边的排序。最终通过一个合并函数，将两个排好序的数组合并成一个数组。
归并排序写起来很简单，说起来也很简单。但是具体是怎么运作的还是很值的深究的。
归并的递归调用，到最后的几个阶段，数组剩下两个元素，又经过一次分治，分别对一个元素进行排序，一个元素的排序很简单——不需要排序。它们执行完毕后，开始执行第一次的merge，然后这两个元素开始有了顺序。紧接着很多个2个元素有了顺序，然后是2个和2个的排序，递归调用开始上升。并最终回归到最初的两个子问题，它们merge成排好序的数组。
堆排序
时间复杂度O(nlogn) 不稳定，空间复杂度O(1).
堆排序说难也难，说容易也容易。如果理解了 完全二叉树->最大堆，那么自然而然就理解了堆排序。
- 完全二叉树：每个节点对多有两个叶子节点，除了最后一层，其它各层每个节点都有两个子节点。
- 最大堆是完全二叉树，最大堆通常使用数组作为数据结构。以数组A为例
int A[] = {-100,1,2,3,4,5,6};
以数组表示最大堆时，为了方便表示，第0个元素通常没什么用（我猜测可以用来存放堆的大小）。从第一个元素开始，以层序存放一颗堆/树，以上面的例子来说，它代表了这样一个结构:
1
/ \
2 3
/\ /
4 5 6
这样存放有一个好处，假设一个节点的下标为i，那么它的左子节点的下标为2i， 它的右子节点的下标为2i+1，而该节点的父亲节点的下标为 i/2（向下取整）。
现在的结构还不算是最大堆，最大堆需要满足这样一个条件:
任何一个节点都必须大于它的两个子节点，因此我们必须对它进行调整，使他成为一个最大堆。也就是如何将一般的数组转换成满足最大堆的数组——最大堆的构建。
构建最大堆
- 堆化函数
构建最大堆以及堆排序，都需要用到一个特别重要的函数，称之为堆化函数。它假设左右两个节点都满足最大堆的性质，而根节点可能小于左右两个子节点。因此将根节点，左右节点中选出一个最大的节点作为新根，旧的根被下降成为新根的子节点。交换之后，当前根成为最大，但是原来的某一个子堆将不满足最大堆的性质。因此递归堆化以子节点为根的堆。
- 利用堆化函数构建最大堆
从倒数第一个非叶子节点开始（也就是上图中的3），依次调用堆化函数，直到到达整个树的根，即数组的第1号元素。这样就得到的最大堆。
堆排序
有了最大堆，堆化函数的概念。如何进行堆排序呢？最大堆的根节点一定是数组最大的元素，因此将该节点与数组最后一个元素进行交换。这样最大的元素被放入了合适的位置。这是堆已经不满足最大堆的性质，因此需要对根节点进行一次堆化（要除了最后一个元素之外）。这样除了已经在最后的最大的元素，其它元素又构成一个最大堆。而第二大的元素成为最大堆的根节点，它与倒数第二个元素交换，然后迭代上述过程。最终得到的数组就是排好序的数组。
因为堆也是在原来的数组上操作的，所以该算法所需的空间复杂度为O(1)。
网友评论