排序算法是计算机科学中最基本、最常用的算法之一。它们能够将一组杂乱无序的数据按照特定的规则进行排列，使得数据更易于理解、搜索和处理。从简单的冒泡排序到高效的快速排序，每个排序算法都有其独特的特点和适用场景。
常用的十大排序算法汇总如下其中稳定性是指排序后两个相等键值的顺序和排序之前它们的顺序相同，图中的In-place表示占用常数内存而不占用额外内存，Out-place表示占用额外内存，n表示数据规模，k表示“桶”的个数；排序算法可以分为内部排序和外部排序：内部排序是数据记录在内存中进行排序，上面的排序算法都是内部排序；外部排序是因为需要排序的数据很大，不能一次性容纳全部的排序记录，故在排序过程中需要访问外存；算法步骤：将“天平”置于待排序序列最右端，比较相邻元素，如果右边元素小于左边元素则交换两个元素，否则不变；“天平”向左移动一位，继续比较左右两端的数；重复1、2步骤，当“天平”移动到最左的时候，其左边的数即使整个序列最小的数，此时将该数提出序列不再参与后续比较；“天平”再次移动到序列最右开始重复上述步骤，直到所有的数字都被排序；最好情况：输入的数据都是正序；最坏情况：输入的数据都是反序；选择排序顾名思义就是简单直观的选择序列中最小的值将其放在序列最前；算法步骤：首先在未排序序列中找到最小元素，存放到排序序列的起始位置；再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾；重复第二步，直到所有元素均排序完毕；插入排序实际上就是我们打扑克牌的常用策略，将最左端的牌固定不变，右边的牌比较大小并插入左边的牌堆；算法步骤：将待排序序列的第一个元素看作是有序序列，第二个元素开始看作是未排序序列；在已排序序列中从后向前扫描，找到相应位置并插入未排序序列的元素；从头到尾依次扫描未排序序列，重复2步骤，将扫描到的每个元素插入到有序序列的适当位置；希尔排序也称为递减增量排序算法，可以看作是插入排序的改进版本；希尔排序的基本思想是：将整个待排序的记录序列分割为若干子序列，在这些子序列中分别进行插入排序，待子序列排序完成后，整个序列呈基本有序状态，此时对全体记录序列进行插入排序；算法步骤：先确定一个增量序列t1,t2.tk，增量会依次减小且最后一个增量一定是1；上述我们确定了k个间隔，所以要进行k趟排序，每趟排序根据间隔的大小将待排序记录分割为若干子序列，对这些子序列进行插入排序；最后依次排序间隔为1也就意味着将整个记录序列使用插入排序进行排序；归并排序是一种建立在归并操作上的一种排序算法，归并排序主要有以下两种实现：自上而下的递归；自下而上的迭代；算法步骤：首先将待排序记录的数字分为两半，一直到只剩下一个数字；合并的时候，按照数字的升序移动，使得合并后的数字在组内按照升序排列；当合并包含多个数字的组的时候，比较开头的数字并移动较小的数字即可；递归重复合并组，直到所有的数字都在一个组中并排序完毕；自下而上迭代实现：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。
自上而下递归实现：对一个数组选中一个中间位置/2），分别进行左递归），右递归），在回朔的时候分别对以中间为分割的数组进行排序），此时是一个归并的过程，这是自上而下的方法。
本质上来看快速排序是建立在冒泡排序的基础上的递归分治法；算法步骤：从数列中挑选一个元素称为基准pivot；所有比pivot小的元素在pivot左边，所有比pivot大的元素在pivot右边；递归地将小于pivot的子序列和大于pivot的子序列使用1、2步骤进行排序；关于如何实现2，我们用下面的图进行解释快速排序实质上就是利用L、R、pivot这些标记递归地重复一系列操作的算法；堆排序利用了堆的数据结构，堆主要有如下两种：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；堆是一种树形结构，是一种特殊的完全二叉树；算法步骤：首先将所有数字存储在堆中，按照降序构建堆；接着逐个取出存储在堆中的数字，取出的数字按照相反的顺序排序可以得到升序序列；算法步骤：根据待排序集合中最大元素和最小元素的差值范围申请额外空间；遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；继续遍历并修改数组，数组遍历完毕后直接遍历输出数组即可桶排序是计数排序的升级版，它利用了函数的映射关系：在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的N个数据均匀分配到K个桶中；对于桶中元素的排序，选择何种排序算法堆性能影响很大；下面这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：基数排序：根据键值的每位数字来分配桶；计数排序：每个桶只存储单一键值；桶排序：每个桶存储一定范围的数值；基数排序是一种非比较排序算法，它根据元素的位值将数据集分成不同的桶或容器，然后按照每个位值上的顺序依次将数据重新组合起来。这个过程会重复进行，直到所有的位都被处理完毕，最终得到一个有序的数据集。
基数排序的基本思想是按照元素的最低位到最高位的顺序进行排序。首先，将所有的元素按照最低位进行一次稳定排序，然后再按照次低位进行排序，依次类推，直到按照最高位进行排序完成。在每一轮排序中，可以使用稳定的排序算法对元素进行排序。
基数排序适用于各个位上的取值范围较小且位数相同的数据集。例如，对于一组整数，如果它们的位数都是相同的，可以使用基数排序来进行排序。
相比于比较排序算法，基数排序的时间复杂度可以达到O(kn)，其中n是元素个数，k是最大元素的位数。尽管基数排序的时间复杂度较低，但它的空间复杂度相对较高，因为需要额外的存储空间来存储每个位值上的桶。
基数排序的优点是稳定性和高效性，尤其适用于位数相同的整数排序。然而，它对数据集的要求较高，如果数据集的位数差异较大，基数排序的效率可能会降低。
