首页 数据结构与算法

# 排序算法开篇

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

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

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

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

# 排序算法好坏的评估

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

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

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

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

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

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

# 排序算法实现

# 交换思想排序

# 分治思想排序

# 线性排序

# 最后

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

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