> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/pai-xu/pai-xu-zong-jie.md).

# 排序总结

**内排序**, **比较算法**总结

| 排序方法 | 平均时间               | 最好时间            | 最差时间            | 空间复杂度          | 是否稳定 |
| ---- | ------------------ | --------------- | --------------- | -------------- | ---- |
| 冒泡   | $$O(n^2)$$         | $$O(n)$$        | $$O(n^2)$$      | $$O(1)$$       | 稳定   |
| 插入   | $$O(n^2)$$         | $$O(n)$$        | $$O(n^2)$$      | $$O(1)$$       | 稳定   |
| 希尔   | $$O(n^{1.25})$$,估计 | -               | -               | $$O(1)$$       | 不稳定  |
| 快速   | $$O(n\log{n})$$    | $$O(n\log{n})$$ | $$O(n^2)$$      | $$O(\log{n})$$ | 不稳定  |
| 归并   | $$O(n\log{n})$$    | $$O(n\log{n})$$ | $$O(n\log{n})$$ | $$O(n)$$       | 稳定   |
| 堆    | $$O(n\log{n})$$    | $$O(n\log{n})$$ | $$O(n\log{n})$$ | $$O(1)$$       | 不稳定  |

**内排序**, **非比较算法**总结

| 排序方法 | 平均时间             | 空间复杂度      | 是否稳定      |
| ---- | ---------------- | ---------- | --------- |
| 计数排序 | $$O(n+k)$$       | $$O(n+k)$$ | 不稳定       |
| 桶排序  | $$O(n+C)$$       | $$O(n+C)$$ | 视桶内排序算法而定 |
| 基数排序 | $$O(d\cdot 2N)$$ | $$O(N+M)$$ | 稳定        |

**计数排序**

对输入是0到$$k$$之间的整数进行排序, 用于小范围的排序, 如0到100之间的排序. 由于计数排序不是比较排序, 排序的速度快于任何比较排序算法.

由于用来计数的数组C的长度取决于待排序数组中数据的范围.

**桶排序**

桶排序是计数排序的变种, 把计数排序中相邻的$$m$$个小桶放到一个大桶中. 在分完桶后, 对每个桶进行排序(例如快排), 然后合并成最后的结果.

桶排序假设序列由一个**随机过程**产生, 该过程将元素均匀而独立地分布在区间\[0,1)上(即提前知道范围). 我们把区间\[0,1)划分成n个相同大小的子区间, 称为桶. 将n个记录分布到各个桶中去. 如果有多于一个记录分到同一个桶中, 需要进行桶内排序. 最后依次把各个桶中的记录列出来记得到有序序列.

桶排序的平均时间复杂度为线性的$$O(n+C)$$, $$C$$为桶内快排的时间复杂度. 如果相对于同样的N, 桶数量M越大, 其效率越高， 最好的时间复杂度达到$$O(N)$$(即计数排序). 桶排序的空间复杂度为$$O(N+M)$$. 此外, 如果桶内的排序算法是稳定算法, 桶排序就是稳定的.

**基数排序**

基本思想为: 将待排数据中的每组关键字**依次**进行**桶分配**. 例子见下面的连接.

基数排序的性能比桶排序要略差, 每一次关键字的桶分配都需要$$O(N)$$的时间复杂度, 而且分配之后得到新的关键字序列又需要$$O(N)$$的时间复杂度(每一次的的关键字都有可能不同). 假如待排数据可以分为$$d$$个关键字, 则基数排序的时间复杂度将是$$O(d\cdot 2N)$$. 空间复杂度为$$O(N+M)$$, $$M$$为桶的数量.

另外, 基数排序是**稳定的**. 注意要保持稳定, 在桶分配完毕后, 对原数组的遍历需要从后向前进行.

关于非比较排序的资料参考:

* [计数排序、桶排序和基数排序](https://segmentfault.com/a/1190000003054515)
* [基数排序与桶排序，计数排序【详解】](https://www.cnblogs.com/ECJTUACM-873284962/p/6935506.html)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/pai-xu/pai-xu-zong-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.