【数据结构】排序：经典排序算法原理解析与优劣对比

什么是排序问题

排序，就是让一组无序数据变成有序的过程。 一般默认这里的有序都是从小到大的排列顺序。下面我们先来讲讲，如何判断不同的排序算法的优劣。

衡量一个排序算法的优劣，我们主要会从以下 3 个角度进行分析：

1．时间复杂度，具体包括，最好时间复杂度、最坏时间复杂度以及平均时间复杂度。

2．空间复杂度，如果空间复杂度为 1，也叫作原地排序。

3．稳定性，排序的稳定性是指相等的数据对象，在排序之后，顺序是否能保证不变。

常见的排序算法及其思想

冒泡排序

1.冒泡排序的原理

从第一个数据开始，依次比较相邻元素的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。通过多轮迭代，直到没有交换操作为止。 冒泡排序就像是在一个水池中处理数据一样，每次会把最大的那个数据传递到最后。

2.冒泡排序的性能

冒泡排序最好时间复杂度是 O(n)，也就是当输入数组刚好是顺序的时候，只需要挨个比较一遍就行了，不需要做交换操作，所以时间复杂度为 O(n)。

冒泡排序最坏时间复杂度会比较惨，是 O(n*n)