Table of Content
实现思想是通过两个相邻元素的比较来把最小或者最大的数交换到最后面
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 交换 | On2 | On | On2 | 稳定 |
实现思想是选择一个最小的数，记录下标，然后与第一个交换
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 选择 | On2 | On2 | On2 | 不稳定 |
实现思想是循环把一个数插入到有序序列中，其实所谓的插入就是不断地向后挪位
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 插入 | On2 | On | On2 | 稳定 |
实现思想是首先选择一个基准元素，一般是第一个元素或者最后一个元素，然后右指针找比基准数小的，左指针找比基准数大的，然后交换，经过几次交换之后，两个指针会相遇在一个数上，然后与基准数交换。这时就会形成基准数的左边的数都比基准数小，右边的数都比基准数大。然后根据同样的方式递归左右两个子序列
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 交换 | Onlog2n | Onlog2n | On2 | 不稳定 |
利用大顶堆可以进行升序，反之，利用小顶堆进行降序排序
例如我们要实现升序，我们就要构造大顶堆，然后把堆顶和最后一个元素交换，然后输出最后一个元素，然后在剩下的元素中再次构造大顶堆，一直递归下去
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 选择 | Onlog2n | Onlog2n | Onlog2n | 不稳定 |
实现思想是按照某一个增量分成若干组，第一次增量为排序数的一半，每组的下标相差都是这个增量，然后每组的全部元素进行插入排序，排序完后，增量减小为原来增量的一半，再次进行分组和排序，当增量为 1，进行插入排序之后，排序完成
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 插入 | On1.3 | On | On2 | 不稳定 |
归并排序就是递归合并，关键是如何将两个有序序列合并成一个，合并的次数为 log2n
合并的算法如下
- 定义变量
i，从 0 开始，依次为 A 序列中每个元素的索引 - 定义就是
j，从 0 开始，依次为 B 序列中每个元素的索引 - 拿
i索引的元素和j索引元素比较，将较小的复制到一个临时数组中 - 如果
i小，i++；如果j小，j++ - 直到其中一个序列里的全部元素都放到临时数组里后，将另一个数组多出来的元素全部放进临时数组里，合并完成
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 归并 | Onlog2n | Onlog2n | Onlog2n | 稳定 |
实现思想是通过收集和分配，分配对数字的个位，十位，百位等关键字进行排序，需要引入 count 和 pos 数组来存放关键字的个数和起始位置，那么我们的数字就不需要比较也不需要交换，直接跟据这个 pos 的值，放到对应的位置，每放置一个数，pos 的值加 1
| 类型 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 基数 | O(d(r+n)) | O(d(n+rd)) | O(d(r+n)) | 稳定 |
d 是数组的长度，n 是关键字的个数，r 是关键字的基数