C++实现排序算法的总结

C++实现排序算法的总结

​​快速排序​​

​​冒泡排序​​

​​插入排序​​

​​希尔排序​​

​​选择排序​​

​​堆排序​​

​​索引最大堆​​

​​归并排序​​

​​外部归并排序​​

​​桶排序​​

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

稳定：插入，冒泡、归并

插入排序，在已经有序的元素中排序，则时间复杂度可以达到O(n)，所以每个排序，面对不同的数据，可能会有不一样的时间复杂度，我们能够给出的就是，平均时间复杂度

总体而言，快速相对来说是比较快的排序算法

原地排序：直接可以在数组上完成排序，不需要再另外开辟空间，所以一些系统对空间相对敏感，则不适合归并排序

快速排序也是原地排序，但是它是利用递归实现，每次递归都需要占用栈空间，所以额外空间为O（logn）,归并排序其实也是递归实现，它的额外空间应该是O（n+logn）但是logn 相对n来说可以忽略不计

对于快速排序的稳定性，首先需要随机选择基准点，很有可能将一批中相等的元素选到了前面，而堆排序，在组建堆的时候，很可能被打乱。

不稳定的排序算法也可以通过自定义函数，使得排序算法稳定（比如重载<比较符）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。