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()尾迭代器就不同了，尾迭代器后面一定有内存空间。