2、算法基础之排序

本文主要是介绍2、算法基础之排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

十大经典排序算法为:

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序
• 计数排序
• 桶排序
• 基数排序

按照平均时间复杂度和最差时间复杂度进行分析以及需要使用额外空间与否,额外空间使用多少来判断排序算法的优劣;
下图是十种排序算法的比较:

名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
. 排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

1.关于时间复杂度各排序算法的比较:
平方阶 (O(n2)) 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

2.关于稳定性各排序方法的比较

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。(辅助记忆冒插归基稳得一批)

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。(辅助记忆希堆快选有点垃圾)
3.快速排序的思想
选择一个数字mid(例如数组选择第一个元素)
将数组分成两部分,大于mid为一部分,小于mid为一部分
会使用到递归来进行不断排序
最后生的数组就是排序好的数组.

参考:
菜鸟教程

这篇关于2、算法基础之排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！