将数据按一定顺序重新排列,称为排序。排序分为升序(从小到大)和降序(从大到小)。排序是许多算法的基础,经过排序的数据往往更容易进行下一步处理。
待排序的数据一般以数组的方式提供,数据的类型既可以是数字,也可以是包含多个属性的对象。当排序对象包含多个属性时,需要确定一个属性作为排序基准,这个属性称为“排序键”(Sort Key)。
对于排序算法,除了要关注复杂度,还需要考虑稳定性。所谓稳定性,是指当数据中存在2个或2个以上的键值相等的元素时,这些元素在排序后的前后顺序不变。比如我们现在要处理一份由“ID”、“问题A得分”、“问题B得分”组成的排名数据,输入顺序如下:
ID | A | B |
---|---|---|
player1 | 70 | 80 |
player2 | 90 | 95 |
player3 | 95 | 60 |
player4 | 80 | 95 |
如果按“问题A得分”进行降序排序,则结果如下:
ID | A | B |
---|---|---|
player3 | 95 | 60 |
player2 | 90 | 95 |
player4 | 80 | 95 |
player1 | 70 | 80 |
如果按“问题B得分”进行降序排序,则会有两种结果,如下:
ID | A | B |
---|---|---|
player2 | 90 | 95 |
player4 | 80 | 95 |
player1 | 70 | 80 |
player3 | 95 | 60 |
ID | A | B |
---|---|---|
player4 | 80 | 95 |
player2 | 90 | 95 |
player1 | 70 | 80 |
player3 | 95 | 60 |
按“问题B得分”排序时,player2和player4得分相同,由于输入时player2在player4前面,所以稳定的排序算法能保证按 player2 -> player4 的顺序输出,而不稳定的排序算法则有可能输出 player4 -> player2 的顺序。
总得来说,在使用排序算法时,需要考虑以下几点:
- 复杂度与稳定性
- 除保存输入数据的数组外是否需要额外申请内存
- 输入数据的特征是否会影响复杂度