基本的排序算法
冒泡排序和插入排序是最基础的，面试官有时候喜欢拿它们来考察你的基础知识，并且看看你能不能快速地写出没有 bug 的代码。
冒泡排序（Bubble Sort）
实现
每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。
复杂度
空间复杂度 O（1）
平均时间复杂度 O（n^2）
稳定的排序算法
插入排序（Insertion Sort）
实现
不断地将尚未排好序的数插入到已经排好序的部分。
复杂度
空间复杂度O（1）
平均时间复杂度O（n^2）
稳定的排序算法
高级的排序算法
归并排序、快速排序和拓扑排序的思想是解决绝大部分涉及排序问题的关键
归并排序
实现
一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
void sort(int[] A, int lo, int hi) {
// 判断是否只剩下最后一个元素
if (lo >= hi) return;
// 从中间将数组分成两个部分
int mid = lo + (hi - lo) / 2;
// 分别递归地将左右两半排好序
sort(A, lo, mid);
sort(A, mid + 1, hi);
// 将排好序的左右两半合并
merge(A, lo, mid, hi);
}
void merge(int[] nums, int lo, int mid, int hi) {
// 复制一份原来的数组
int[] copy = nums.clone();
// 定义一个 k 指针表示从什么位置开始修改原来的数组
// i 指针表示左半边的起始位置，j 表示右半边的起始位置
int k = lo, i = lo, j = mid + 1;
while (k <= hi) {
if (i > mid) {
nums[k++] = copy[j++];
} else if (j > hi) {
nums[k++] = copy[i++];
} else if (copy[j] < copy[i]) {
nums[k++] = copy[j++];
} else {
nums[k++] = copy[i++];
}
}
}
复杂度
时间复杂度O(nlogn)
对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是O(nlogn)
空间复杂度 O(n)
由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)
归并排序也是稳定的排序算法
总结
归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。
快速排序（Quick Sort）
实现
利用基准值来将原数组分为两个子数组，然后分别对每个子数组排序
void sort(int[] nums, int lo, int hi) {
if (lo >= hi) return; // 判断是否只剩下一个元素，是，则直接返回
// 利用 partition 函数找到一个随机的基准点
int p = partition(nums, lo, hi);
// 递归地对基准点左半边和右半边的数进行排序
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
int partition(int[] nums, int lo, int hi) {
// 随机选择一个数作为基准值，nums[hi] 就是基准值
swap(nums, randRange(lo, hi), hi);
int i, j;
// 从左到右用每个数和基准值比较，若比基准值小，则放到指针 i 所指向的位置
// 循环完毕后，i 指针之前的数都比基准值小
for (i = lo, j = lo; j < hi; j++) {
if (nums[j] <= nums[hi]) {
swap(nums, i++, j);
}
}
// 末尾的基准值放置到指针 i 的位置，i 指针之后的数都比基准值大
swap(nums, i, j);
// 返回指针 i，作为基准点的位置
return i;
}
复杂度
时间复杂度
最优情况：被选出来的基准值都是当前子数组的中间数。O(nlogn)
最坏情况：基准值选择了子数组里的最大或者最小值。O(n^2)
空间复杂度
和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是 O(logn)。
不稳定排序
解法总结
-
快排拓展
题目 思路 215. 数组中的第K个最大元素