关于排序，你必须知道的

排序介绍

排序是按顺序重新排列给定序列中元素的行为，可以按字典顺序排列，可以按数字的升序或降序排列，也可以按照你指定的规则去排列。

一些基本的时间复杂度为O(n^2)的排序算法，在面试编码的时候尽量不要使用，除非面试官要求你实现一个冒泡排序或选择排序。大部分时候是不太可能要求你从头实现某一个排序算法。一般都是使用语言自带的排序算法，但你需要熟知自己擅长语言中排序算法的原理。排序经常跟二分查找一起出现在面试题中。

一个已排序的元素数组，利用其已排序的属性，使用二分查找可以在O(logn)时间内完成一个指定元素的搜索。二分查找将目标值与数组的中间元素进行比较，来决定是在数组的左半边还是右半边查找目标值，然后在符合条件的半边继续进行二分查找，直到找到目标或符合条件的半边为空。

常见排序算法的时空复杂度

算法名称	时间复杂度	空间复杂度
冒泡排序	O(n^2)	O(1)
插入排序	O(n^2)	O(1)
选择排序	O(n^2)	O(1)
快速排序	O(nlogn)	O(logn)
归并排序	O(nlogn)	O(n)
堆排序	O(nlogn)	O(1)
计数排序	O(n + k)	O(k)
基数排序	O(nk)	O(n + k)

上面的复杂度都是平均的复杂度，有些算法的时间复杂度跟给定序列是否基本有序相关，比如快排，越是有序的序列排起序来就越慢。

基于有序序列的二分查找的时间复杂度为O(logn)。

排序涉及的一些边界条件

• 给定的序列为空
• 给定的序列只有一个元素
• 给定的序列只有两个元素
• 给定的序列包含重复元素

一些小技巧

1. 当给定的序列是有序的(升序或降序)时，首先应该想到的就是使用二分查找。
2. 计数排序不是基于比较的排序，如果事先知道给定序列值的范围，使用计数排序是一种不错的选择。