# sort-Summary

## 稳定性

在对同一组数据进行多种标准的排序时非常有用,当然稳定性对基础类型的作用不大，稳定性一般用于符合类型。

| 排序种类 |     时间复杂度     |    空间复杂度   |  稳定性 |
| :--: | :-----------: | :--------: | :--: |
| 选择排序 |    $O(N^2)$   |   $O(1)$   |  不稳定 |
| 插入排序 |    $O(N^2)$   |   $O(1)$   | 可以稳定 |
| 冒泡排序 |    $O(N^2)$   |   $O(1)$   | 可以稳定 |
| 归并排序 | $O(N\*log N)$ |   $O(N)$   | 可以稳定 |
| 快速排序 | $O(N\*log N)$ | $O(log N)$ |  不稳定 |
|  堆排序 | $O(N\*logN) $ |   $O(1)$   |  不稳定 |
|  桶排序 |     $O(N)$    |   $O(M)$   |  稳定  |

**稳定性分析** 目标序列：{3，3，2，2，1，4}

* 选择：不具备稳定性，交换时可能会位置交换，比如当前指针指向最小值1，随后将与左3交换，于是左3与右3位置交换，不具备稳定性
* 冒泡：具备稳定性，**相等时不往前冒就行**，比如当前指针指向右3，与左3相等，于是停止此轮冒泡即可保持稳定性。
* 插入：具备 **相等时不往前插就行**，同样当前指针指向3，与左3相等，停止此轮插入即可保持稳定性。
* 归并：可以保持稳定性。在合并左右序列时，如果左值与右值相等，先拷贝左值即可保持稳定性。比如左序列{1，2，5}，右序列{2，6，8}。先拷贝左值就保持了原始序列中两个2的顺序。如果先拷贝右值就丧失了稳定性。
* 快排：不稳定，parition过程中在将数据交换至小于区域会调换相等区域数据的顺序。比如{2，3，5，5，4，6，7，8，5}，基值num为5，在处理数据4时，其会与等于区域的左5交换，导致左5与右5顺序交换。
* 堆排：不稳定 重新调整时会破坏稳定性，比如堆{5，5}，此时插入数据6，调整6时会将左5调整至最后，左4与右5顺序交换，丧失稳定性。
* 桶排序 稳定(非比较排序)，因为入桶和出桶操作是一个队列操作，先进先出，不会导致顺序交换

## 结论

* 如果只想最快排序，选择随机快排，因为随机快排的常数时间最小
* 在乎稳定性，选择归并排序
* 如果在乎空间，选择堆排序

**常见坑**

* 归并额外空间可以为O(1)但是没必要
* 快排可以做到稳定性，但是没必要

**一道没事找事的题目** 要求处理序列，将奇数放左边，偶数放右边，做到$O(N)$和$O(1)$也是两个标准 注意这道题目堆序列分割有两个要求：奇数和偶数；而快排也是两个要求：大于num的和小于num。快排都做到$O(N)$和$O(1)$的要求，这道题目自然也不可能完成。 所以：

**工程上的改进**

* 稳定性的保留，将$O(N\*log N)$和$O(N^2)$的排序结合，要考虑常数项以及数据长度，并且插入排序的常数项远低于快排

**杂项**

* 对于哈希表&有序表，基础类型在表中是按值传递的，对于复合类型，表内是按引用传递的。
* **关于c++的`begin()`首迭代器，当首迭代器为0时就不能再减了！因为首迭代器前面可能没有内存空间了。但是`end()`尾迭代器就不同了，尾迭代器后面一定有内存空间。**
