数据结构与算法中，有哪些十大排序算法的要点总结？

本文共计6628个文字，预计阅读时间需要27分钟。

0.1 排序算法说明：0.1 排序算法定义：对一组对象根据某个关键字进行排序的过程。

0.2 术语说明：稳定：若a原本在b前面，且a=b，排序后a仍然在b前面；不稳定：若a原本在b前面，且a=b，排序后a可能不在b前面。

0、排序算法说明

0.1 排序的定义： 对一序列对象根据某个关键字进行排序。

0.2 术语说明

• 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
• 不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
• 内排序 ：所有排序操作都在内存中完成；
• 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度 ： 一个算法执行所耗费的时间。
• 空间复杂度 ：运行完一个程序所需内存的大小。

0.3 算法总结

比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序 等属于比较排序 。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。

在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。