最近找工作面试，真的是被数据结构和算法给反复吊打了。

平时做项目基本都是在写业务逻辑，即使遇到了关于数据结构算法的东西，也是一个接口调用搞定。

基础的一些东西反而薄弱了，拿排序算法来说吧，长时间不写，光是记清楚算法复杂度就够呛了，更别说手撸算法了。

痛定思痛，决心还是放低心态，从基础做起，把每个算法亲手敲一遍。

排序算法是最基础的算法，也是面试官比较容易问到的算法。就像相声演员需要联系 “说学逗唱” 四门基本功一样。

这个排序算法就是程序员的基本功。

如果面试中连排序算法都答不上来，就基本凉凉了，其他的扯再多也没用了。

哎说多了都是泪，下面好好复习一下把。

常用的排序算法主要有以下 7 种，本文主要对这 7 种排序算法进行整理分析和比较。

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 快速排序
5. 希尔排序
6. 归并排序
7. 堆排序

1. 冒泡排序

就是将小的数字慢慢往上 “冒泡”，大的数字慢慢往下 “沉底”。

每次从数组的最后面开始循环，如果一个数比它前面的数字小，那么就交换位置。

这样每循环一次，就将一个最小值 “上浮” 到数组前面，跟冒泡一样。

复杂度：

每循环一次，就有一个值排到了正确的位置，若要全部排好，需要循环 n 次。所以时间复杂度为 O(n^2)。

整个排序过程只用到了一个中间变量，不需要额外的存储空间，所以空间复杂度为 O(1)。

稳定性：稳定

2. 选择排序

在数组的未排序的部分中，每次循环都找出一个最小值，将这个最小值直接交换到未排序部分的最前面。

然后将选出来的这个值加入到已排序的部分中。

总的来说就是，每次遍历都选择一个剩余数中最小的值，所以叫选择排序嘛。

复杂度：

每循环一次，选择一个最小值出来排序，所以全部完成排序需要 n 次循环，时间复杂度为 O(n^2)。

同样属于内部排序，不需要额外的存储空间，所以空间复杂度为 O(1)。

稳定性：不稳定

3. 插入排序

数组分成两部分，未排序部分和已排序部分。

每次从未排序部分中按顺序取出一个值，插入到已排序部分中的对应位置。

复杂度：

插入排序需要要插入n次，每次插入时，需要遍历数组已排序的部分寻找插入点，并将插入点后面的元素全部后挪一位，所以时间复杂度为 O(n^2)。

虽然数组分成未排序部分和已排序部分两部分来分别处理，但只是逻辑上的分开，实际上还是属于内部排序，不需要借助额外的存储空间，所以空间复杂度为 O(1)。

稳定性：稳定

4. 快速排序

选取一个基准元素，将数组中所有小于基准元素的值挪到其左侧，所有大于等于基准元素的值挪到其右侧。

在左侧和右侧的序列中分别再选一个基准元素，递归地方式重复进行上面的操作。

直到基准元素的左右列表都为空，即完成了排序。

复杂度：

每取数组中一个元素为基准，分成左右两个部分分别进行排序，平均情况下，要递归 log2n 层。所以快速排序的时间复杂度为 O(nLog2n)。

快速排序由于平均需要递归 log2n 层，所以需要的空间复杂度为 O(log2n)。

稳定性：不稳定

5. 希尔排序

插入排序的进阶版，改变步长来减少元素的移动次数。步长为1时就是普通的插入排序。

步长初始为数组长的一半，此后，步长每次减半，直到为 1 。

复杂度：

在步长减为 1 之前，可以将用较少的移动次数，把数组排成接近有序状态，步长减为 1 时，就成了普通的插入排序，所以希尔排序的时间复杂度要比插入排序稍微低一些，大概是 O(n^1.3) 左右（未验证）。

在空间复杂度方面，依然跟插入排序一致，为 O(1)。

稳定性：不稳定

6. 归并排序

使用递归-分治的思想，将数组向下递归，拆分成单个的元素，然后向上拼接，成为完整数组。

每次拼接完成的操作就是 将两个有序数组拼接成一个新的有序数组。

复杂度：

由于使用递归分治的方式，每次将子序列两两拼接，所以时间复杂度为 O(nLog2n)。

归并算法属于用空间换时间，使用了 n 的额外辅助空间，所以空间复杂度为 O(n)。

稳定性：稳定

7. 堆排序

借助 二叉堆中的最大堆 来完成排序。

用数组中的元素构造最大堆，然后每次取根节点元素（最大值）出来，加入到已排序部分。

复杂度：

由于使用了二叉堆的结构，时间复杂度为 O(nLog2n)。

空间复杂度为 O(1)。

稳定性：不稳定

下面对各种排序算法进行比较，方便记忆。

时间复杂度

O(n^2) ：选择排序，插入排序，冒泡排序（三个都是两层 for 循环嵌套）

O(n^1.3) ：希尔排序

O(nLog2n) ：快速排序，归并排序，堆排序（前两个用了递归分支的思想，第三个用了二叉堆结构）

空间复杂度

O(1) ：插入排序，选择排序，冒泡排序，希尔排序，堆排序

O(n) ：归并排序（空间换时间）

O(log2n) ：快速排序（空间换时间）

稳定性

稳定：插入排序，冒泡排序，归并排序

不稳定：希尔排序，选择排序，快速排序，堆排序