本文的排序以升序为例

1、冒泡排序

算法原理：从第一个元素开始，与未排定顺序后面的所有元素比较，将最大的元素放到参与比较的所有元素的最后一位，如此经过n-1轮循环排序得出最终结果。其时间复杂度为O(n2)，空间复杂度是O(1)。代码如下：

交换位置 冒泡排序

2、选择排序

算法原理：从未完成排序的第一个元素开始，与后面的元素比较，得到最小元素的下标min，然后拿到下标min对应的元素与未完成排序元素的第一个元素交换位置，这样循环n-1轮完成排序。其时间复杂度为O(n2)，空间复杂度是O(1)。与冒泡排序比较，减少了元素交换的频率。代码如下：

选择排序

3、插入排序：

算法原理：从第二个元素开始temp，与之前的元素比较（已经排好序），从后往前比（也可以从前往后比，本文从后往前比），如果比temp大，则元素往后挪动一位，反之，则将temp赋值给与之比较的元素所在下标加1的位置，这样循环n-1轮后完成排序。其时间复杂度为O(n2)，空间复杂度是O(1)。与前两者比较，虽然没有元素的交换，但是存在挪动元素位置。代码如下：

插入排序

4、堆排序：

算法原理：

4.1、堆（完全二叉树）

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆

大顶堆堆映射到数组的逻辑结构如下：

大顶堆映射素组

将一个数组调整成大顶堆的代码如下：

调整成大顶堆

4.2、堆排序的算法原理：

首先将数组调整成大顶堆逻辑结构，然后将大顶堆的对顶元素跟末尾元素位置互换，继续将除末尾元素之外的子数组调整成大顶堆结构，如此循环n-1次完成排序。其时间复杂度为O(n*log2n)，空间复杂度是O(1)。与前面三者相比，时间复杂度减少了，但是不够稳定。代码如下：

堆排序

5、快速排序：

算法原理：从数组中取一个数为标准值s（一般是数组的开头或者结尾，本文以开头为标准），从数组的两端开始（如果以一端为标准，则从另一端开始查找），本文以左端为基准值s，从右端开始查找，找到一个比标准值s小的数，并记录该位置i，然后从左端开始，找到一个比标准值s大的值并记录该位置j，如果两个位置不相等，交换位置，从查找的位置开始，循环上述操作，直到i==j，然后将i位置的值跟标准值s交换，此时i左边全部为比标准值s小的数，右边全部为比标准值s大的数，然后将以i为分界线分成两组，重复上述操作，直到不能分组，排序完成。其时间复杂度为O(n*log2n)~O(n2)，空间复杂度是O(log2n)~O(n)。不稳定。代码如下：

快速排序

6、希尔排序：

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法：将数组按照希尔增量进行分组，然后在各个小组内进行插入排序，完成后，成倍见效增量，继续分组，同样在组内进行插入排序，这样到最后不能分组，排序完成。时间复杂度跟选择的增量有很大的关系，虽然目前找到了比较好的增量，但是不确定是最好的，因此最好的情况暂时没有确定，最差的情况是O(N*logN)。空间复杂度为O(1)。算法图解如下：

希尔算法图解

代码如下：

希尔算法

好了，本文暂时写到这，欢迎指正

参考：

常用的排序算法的时间复杂度和空间复杂度

图解排序算法(二)之希尔排序