一、引言
练好基本功，面试中经常考察的排序算法有快速排序、归并排序、插入排序、冒泡排序、堆排序和计数排序等。学习排序算法时需要关注以下几点：
- 时间复杂度
- 空间复杂度
- 排序算法的稳定性
- 算法适用的场景
二、快速排序
快排基本思路是找一个基准元素 pivot，把数组分成 2 部分（这 2 部分都不包括pivot），再分别递归快排这 2 个子数组。平均时间复杂度 O(NlogN),空间复杂度O(logN)。
相同大小的元素在比较过程中会改变相对顺序（比如最右边的先交换到左边），所以快排是不稳定排序。
/**
* 快速排序，先找到 pivot 元素在数组中排序后的最终位置；再对 pivot 左边区间和右边区间的子数组继续进行快速排序
* @param arr
* @param start
* @param end
*/
public void quicksort(int[] arr, int start, int end) {
if(start >= end) return;
int left = start, right = end;
int pivot = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivot) {
--right;
}
if(left < right) {
arr[left] = arr[right];
}
while(left < right && arr[left] <= pivot) {
++left;
}
if(left < right) {
arr[right] = arr[left];
}
}
arr[left] = pivot;
quicksort(arr, start, left -1);
quicksort(arr, left + 1, end);
}三、归并排序
归并排序先把数组拆分为 2 个子数组并对子数组排序，对 2 个排号序的子数组进行归并。对子数组排序是一个递归调用过程，只是问题空间变小了，也就是能收敛。
相对快速排序，归并排序优点是算法是稳定的，也就是相同元素相对位置不会变，缺点是需要 O(N)的空间复杂度。
归并排序和快速排序都有分而治之的设计思想，把一个大的问题空间拆分成小的问题空间。如果按拆分类似 2 叉树的角度来看，快速排序是前序遍历（先找 pivot 节点位置），归并排序是后序（归并操作在最后）。
/**
* 归并排序 2：内存只分配一次
* @param arr：原数组
* @param temp：临时数组，和原数组大小一致
* @param left：待排序数组左边界。需要指定的原因是递归调用需要修改待排序子数组边界
* @param right：待排序数组右边界
*/
public void mergeSort2(int[] arr, int[] temp, int left, int right) {
if(left >= right) return;
int mid = left + (right - left) / 2;
mergeSort2(arr, temp, left, mid);
mergeSort2(arr, temp, mid + 1, right);
merge2(arr, temp, left, mid, right);
}
/**
* 合并数组，对应归并数组 2。temp 数组 k 位置也可以从 0 开始，只要保证来回复制时位置一致即可（程序没有并发）
* @param arr：原始数组
* @param temp：临时数组
* @param start：左子数组开始位置
* @param mid：二分的中间位置，并归入左子数组右边界
* @param end：右子数组结束位置
*/
private void merge2(int[] arr, int[] temp, int start, int mid, int end) {
int i = start, j = mid + 1, k = start;
while(i <= mid && j <= end) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while(i <= mid) temp[k++] = arr[i++];
while(j <= end) temp[k++] = arr[j++];
// 原始数组从临时数组中还原
System.arraycopy(temp, start, arr, start, end - start + 1);
}四、Java 中 Arrays.sort使用的排序算法
数据量大用快速排序或者归并排序，数据量小用插入排序。
五. 算法复杂度
具体算法时间或者空间复杂度以及稳定性可以参考维基百科。
六、总结
本文介绍了几种常见的算法面试中遇到的排序算法，实现算法的方式很多，网上找一大把，读者主要从算法思想来了解算法的优势和劣势。一般基于比较和交换的排序算法平均时间复杂度到 O(Nlog(N))已经不错了，插入、选择和冒泡等排序算法平均时间复杂度为O(N^2)。还有一种更牛的基于计数的时间复杂度为O(N+K)，K为数的范围，当然这种需要待排序的数在一定范围内。