排序算法

排序算法开篇

排序算法有很多,比如常见的 冒泡排序,插入排序,选择排序,归并排序,快速排序,计数排序,基数排序,桶排序, 还有不常见的猴子排序,睡眠排序,面条排序等。

其中, 冒泡排序,插入排序, 选择排序 的时间复杂度都是$O(n^2)$

快排,归并排序 的时间复杂度是 $O(nlogn)$

桶排序，计数排序,基数排序的时间复杂度是 $O(n)$

排序算法好坏的评估

• 最好情况,最坏情况,平均情况的时间复杂度 我们要知道排序算法在不同数据下的性能表现。

• 时间复杂度的系数,常数,低阶 时间复杂度反应的是数据规模n很大的时候的一个增长趋势,所以它表示的时候,会忽略系数,常数，低阶.但是我排序的时候，涉及到的数据是很小规模的，所以我们需要考虑下系数，常数，低阶。

• 比较次数和交换(移动)次数 在基于比较的排序算法的执行过程中，最多的会涉及两种操作, 元素比较大小和元素交换或移动.

• 内存消耗 即空间复杂度。

• 排序算法的稳定性 稳定性是指: 如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。 这样的排序算法有什么好处呢?

  假设有这样一个需求, 对一些学生的成绩进行排序. 按照总成绩从大到小的顺序进行排列.总成绩相等的按照数学成绩从大到小的顺序进行排列。这时，我们就可以使用稳定的排序算法. 先按照数学成绩从大到小的顺序进行排列,这样保证了数学成绩是有序的,然后我们再对总成绩进行排序,这样就满足了整体需求了.

排序算法实现

交换思想排序

• :point_right: 冒泡排序
• :point_right: 选择排序
• 插入排序

分治思想排序

• :point_right: 归并排序
• :point_right: 快速排序

线性排序

• :point_right: 桶排序(Bubble Sort)
• 计数排序 (Counting Sort)
• 基数排序(Radix Sort)
• 堆排序

最后

期望与你一起遇见更好的自己