排序算法 | 好急好急的Hexo博客

选择排序：相当于每次都找最小的插到前面

具体实现是：在数组中设定一个sortedIndex，序号小于sortedIndex代表已经排好序的，序号大于等于sortedIndex的就是没排序的。然后每次就是在没排序的里面找最小的，把这个最小的和arr[sortedIndex]交换值即可，然后sortedIndex++

这个算法的复杂度是On^2，并且不稳定，会改变相同元素的相对位置

冒泡排序：相比选择排序，冒泡是把序号大于等于sortedIndex的进行前后项交换

具体实现是：从后往前遍历，如果后项小于前项，交换两者，否则不变。如此一来，arr[sortedIndex]就是序号大于等于sortedIndex里最小的那个了

复杂度也是On^2，但是是稳定的

插入排序：从第二个元素开始，把这个元素插入到已排完序部分的适当位置

就是一开始第一个元素认为是有序的，然后从第二个开始，再去插入到已经排好序的数组中去。在插入过程中，是从sortedIndex（目前arr[sortedIndex]就是那个插入的元素）开始往前遍历，若后项小于前项，则交换。

复杂度On^2，不过若数组有序度比较高，那这个插入操作就不需要了，相当于复杂度为On，这个算法也是稳定的

希尔排序：思路是先提升整个数组的有序度，再用插入排序

相当于按一定分组进行插入排序，这里是设置了一个h变量（最开始是比较大的），然后就是每隔h的元素间进行插入排序；随后逐渐减小h至1（当h=1时就是普通插入排序）

复杂度反正比On^2强，不好具体计算，不过是不稳定的

快速排序：选定随机元素后，对着该元素两边的数组进行递归排序

数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

快速排序首先要选择一个元素作为枢轴（pivot），这个的选取是纯随机的，然后需要调整数组使得pivot左边的值都小于等于arr[pivot]，pivot右边的值都大于等于arr[pivot]，这个的调整方法是：

例如把数组首位设置为pivot，那么定义变量pivot=arr[0]，然后定义两个指针left和right，初始位置即数组两段，left从左往右扫，right从右往左扫；left负责把比pivot大的搬到右边，right负责把比pivot小的搬到左边。在这里“把数组首位设置为pivot”的情况下，因为只有arr[0]是空的，所以首先由right将右边比pivot小的元素塞到左边，一直这样子下去，最后会在数组中出现一个空位，空位里塞pivot即可，在最终结果中，pivot左边的都小于等于它，右边的都大于等于它。

随后就是递归过程，对pivot左边的（右边的）同样都选一个新pivot，不断做，直到这个pivot两边元素只剩1个或为空。

归并排序：分组执行归并操作

啥是归并操作？

就是如何把两个有序的数组合并为一个，其操作方式为：对两个数组都设定一个指针指向首元素，然后每次都比较两个指针指向的元素大小，谁小就把该元素存到一个临时数组中，并且指针向后移一位。如果某个数组已经全部取完，那么剩下数组中的元素就直接接到临时数组中去即可。

在归并排序中，首先将每个元素都视作一个个长度为1的数组，他们都是有序的。然后每轮都对相邻的两个数组做归并

堆排序：先对原数组建小根堆，然后不断弹出最小根即可

堆是这样的：首先是完全二叉树，即只有最后一行不为满，且最后一行必须从左向右排列，然后堆分为小根堆和大根堆，区别如下：

小根堆即每个根节点都小于其所有子节点

大根堆即每个根节点都大于其所有子节点

然后堆主要有两个操作（以小根堆为例）：

上浮：子节点很小，需要将子节点与父节点交换让子节点上去

下沉：根节点很大，需要把根节点放下去

在堆排序中，先对数组建小根堆，然后每次都输出最小的根节点，然后把最右下角的子节点补上最小根节点的空缺，重新再做下沉操作构建堆。就这样一直输出最小根即排序

计数排序：这个很好理解，先统计原数组中每个元素的出现次数，然后把每个元素从小到大根据其出现次数放入新数组即可

桶排序：这个使用的是分治的思想。根据数组中值的分布，创建多个桶（每个桶代表不同的取值范围），尽量确保每个桶中元素的个数差不多。然后在每个桶中进行排序（随便用什么排序算法），最后把每个桶的结果取出来即可组合成一个已经排完序的数组。

基数排序：这个排序不是基于比较去实现的，是一种逐位排序的方法。

数据结构合集 - 基数排序(算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

所谓“基数”，就是代表进制。

基数排序的流程是这样的：

首先先将数组中所有元素的位数统一（通过补前导0），在这里我们只考虑十进制数这种可能性，我们会创建10个桶（分别代表个位为0~10）：

首先排个位上的值：将数组中的元素按个位放到对应的桶中，然后再按从0到9的顺序把各数取出，形成新数组；

然后排十位上的值：与上面一致，按上面新数组的顺序将各元素按十位放入对应的桶中，然后再取出

就这样一直做下去，直到最高位也排完就结束了