破阵子·春景
燕子来时新社，梨花落后清明。
池上碧苔三四点，叶底黄鹂一两声。日长飞絮轻。
巧笑同桌伙伴，上学径里逢迎。
疑怪昨宵春梦好，元是今朝Offer拿。笑从双脸生。
排序算法——最基础的算法，互联网面试必备技能。春来来了，排序的季节来了！
本文使用Java语言优雅地实现常用排序算法，希望对大家有帮助，早日拿到Offer！
冒泡排序
最暴力、最无脑、最简单的排序算法。名字的由来是因为越大的元素会经由交换慢慢“浮”到数组的顶端，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
冒泡排序的基本思想是：每次比较相邻的元素，如果它们的顺序和理想顺序不一致，就把它们进行交换。不多叨叨了，直接看代码。
public static void bubbleSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
//冒泡排序，遇到乱序不管三七二十一直接交换完事
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
选择排序
选择排序，这样记忆，选择最小的元素与未进行排序的首元素进行交换。
选择排序具体过程：
- 找到数组中最小的元素，将它与数组的第一个元素交换位置；
- 在剩下的元素中寻找最小的元素，将它和数组第二个元素交换位置；
- 往复执行，直到将整个数组排序完成。
选择排序特点：
- 运行时间和输入无关；选择排序为了找到最小的元素需要每次都扫描一遍整个输入数组，这也是它的平均时间复杂度、最好情况、最坏情况都是O（n^2）。
- 数据移动最少；每次交换都会改变两个数组元素的值，交换次数和要排序的数组大小呈线性关系。
public static void selectSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
//选择排序，每次选择最小的元素与未进行排序的首元素进行交换
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
插入排序
插入排序，这样记忆，将一个元素插入到已经排好序的有序数组中。
插入排序的基本思想是：每步将一个待排序的元素，插入前面已经排序的数组中适当位置上，直到全部插入完为止。
在程序的实现中，为了给要插入的元素腾出空间，需要将其余所有元素在插入之前都向右移动一位。
插入排序所需的时间取决于输入元素的初始顺序，对数据量比较大且基本有序的数组进行排序要比对随机顺序或者逆序数组排序要快的多。
public static void insertSort(int[] arr) {
int n = arr.length;
if (n <= 1) {
return;
}
//插入排序：找到位置，将其余所有元素在插入之前都向右移动一位
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr, j, j - 1);
}
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
希尔排序
希尔排序是1959年Shell发明，是第一个突破O（n^2）的排序算法，是简单插入排序的改进版。与插入排序的不同之处在于，它会优先比较距离较远的元素。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
关于希尔排序的时间复杂度，有人在大量的实验之后得出结论：当n在某个特定的范围后希尔排序的比较和移动次数减少至n^1.3 ，关于数学论证，这就很困难了。这种科学难题我们就不用太纠结了。
public static void shellSort(int[] arr) {
int n = arr.length;
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;//1,4,13,40,121,364,1093, ...
}
while (h >= 1) {
//将数组变为h有序
for (int i = h; i < n; i++) {
//将arr[i]插入到arr[i-h],arrr[i-2*h],arr[i-3*h]...中
for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
swap(arr, j, j - h);
}
}
h = h / 3;
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
快速排序
重要！重要！重要！>在现场笔试和面试中遇到好多次了（阿里巴巴、字节跳动、腾讯、百度等）。
与冒泡排序相比，快速排序每次交换是跳跃式的，这也是快速排序速度较快的原因。每次排序的时候选择一个基准点，将小于基准点的全部放到基准点左边，将大于基准点的都放到基准点右边。这样每次交换的时候就不会想冒泡排序一样只交换相邻位置的元素，交换距离变大，交换次数变小，从而提高速度。当然在最坏情况下，仍可能是相邻两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，都是O（n^2）。快速排序的平均时间复杂度为O（nlogn）。而且，快速排序是原地排序（只需要一个很小的辅助栈），时间和空间复杂度都很优秀。用《算法（第四版）》的话来说就是：
快速排序是最快的通用排序算法。
程序怎么写：
- 定义一个基准数（初始化值设置为左边第一个元素）和两个左右指针（分别为i和j）；
- 当i和j没有相遇的时候，在循环中进行寻找i和j，让j先从右往左寻找比基准数小的，i从左往右寻找比基准数大的，当然需要满足条件
i<j；找到了的时候，进行交换。为什么要右边的指针先走呢？当从左边开始时，那么 i 所停留的那个位置肯定是大于基数base的，为了满足i<j的条件，j也会停下。那么如果在此时进行交换，会发现交换以后并不满足基准数左边都比基准数小，右边都比基准数大。 - 当i和j相遇的时候，说明i右边已经没有比基准数base小的元素了，左边没有比基准数大的元素了，此时交换i位置上的元素arr[i]和基准数，基准数的位置就定好了。
- 基准数归位
- 继续快速排序处理i的左半部分和右半部分。
如果理解了，自己能写出来最好。如果还没有完全理解，需要进行面试，那我觉得还是背下来吧。对，没有看错，就是背下来，现场笔试的时候直接默写！！！
public static void quickSort(int[] arr, int left, int right){
if(left > right){
return;
}
int base = arr[0];//基准数
int i = left;
int j = right;
//i和j没有相遇，在循环中进行检索
while(i != j){
//先由j从右往左检索比基准数小的，找到就停下
while(arr[j] >= base && i < j){
j--;
}
//i从左往右检索比基准数大的，找到就停下
while(arr[i] <= base && i < j){
i++;
}
//此时，找到了i和j，进行交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//基准数归位
arr[left] = arr[i];//相遇位置的元素赋值给基准位置的元素
arr[i] = base;//基准数赋值给相遇位置的元素
//此时，i左边的都比i小，右边的都比i大；再进行快速排序
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
归并排序
上文提到，快速排序是最快的通用排序算法。的确，在大多数情况下，快速排序是最佳选择。但是，有一个明显的例外：如果稳定性很重要且空间又不是问题，归并排序可能是最好的。
归并排序是分治思想（divide-and-conquer）的典型应用。将待排序的数组，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
归并排序的优点是能够保证将任意长度为n的数组排序所需的时间与nlogn成正比，时间复杂度为O（nlogn）；缺点也很明显，所需的额外空间与n成正比，空间复杂度O（n）。
/**
*
* @param arr
* 待归并的数组
* @param l
* 左边界
* @param mid
* 中
* @param r
* 右边界
*/
public static void merge(int[] arr, int l, int mid, int r) {
int[] aux = Arrays.copyOfRange(arr, 0, arr.length);//复制数组
//将[l,mid]和[mid+1,r]归并
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid)
arr[k] = aux[j++];
else if (j > r)
arr[k] = aux[i++];
else if (aux[j] < aux[i]) {
arr[k] = aux[j++];
} else {
arr[k] = aux[i++];
}
}
}
public static void sort(int[] arr, int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
sort(arr, l, mid);//左边归并排序
sort(arr, mid + 1, r);//右边归并排序
merge(arr, l, mid, r);//将两个有序子数组合并
}
public static void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
堆排序
堆排序，首要问题是要知道什么是堆？
通俗来说，堆是一种特殊的完全二叉树。如果这课二叉树所有父节点都要比子节点大，就叫大顶堆；如果所有父节点都比子节点小，就叫小顶堆。
《算法（第四版）》是这么说的：
当一棵二叉树的每个节点都大于等于它的两个节点时，它被称为堆有序。
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层序存储。
也就是说：对于n个元素的待排序数组arr[0，...，n-1]，当且仅当满足下列要求（0 <= i <= (n-1)/2）：
array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；
array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
堆排序的基本思想（大顶堆为例）：将待排序数组构造成一个大顶堆，此时，整个数组的最大值就是堆顶元素。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，就可以得到一个有序数组。
具体过程：
- 建堆；
- 将堆顶元素与堆底元素进行交换；
- 堆顶元素向下调整使其继续保持大根堆的性质；
- 重复过程2,3，直到堆中只剩下堆顶元素未交换，此时也无法交换了，排序完成。
其中建堆的时间复杂度为O（n）；
由于堆的高度为logn，所以将堆顶元素与堆底元素进行交换并进行排序的时间复杂度为O（logn）；
所以整体的时间复杂度为O（nlogn）。
堆排序过程中只有交换的时候借助了辅助空间，空间复杂度为O（1）。
/**
*
* @param arr
* 要进行堆排序的数组
* @param n
* 数组元素个数
* @param i
* 对节点i进行heapify操作
*/
public static void heapify(int[] arr, int n, int i) {
if (i >= n) {
return;
}
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;//假设最大的为arr[i]
//取左右孩子中较大者的进行交换
if (c1 < n && arr[c1] > arr[max]) {
max = c1;
}
if (c2 < n && arr[c2] > arr[max]) {
max = c2;
}
if (max != i) {
swap(arr, max, i);
heapify(arr, n, max);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void buildHeap(int arr[], int n) {
int lastNode = n - 1;
int parent = (lastNode - 1) / 2;
//从最后一个节点的父节点开始，直到根节点0，反复调整堆heapify
for (int i = parent; i >= 0; i--) {
heapify(arr, n, i);
}
}
public static void heapSort(int[] arr, int n) {
buildHeap(arr, n);
for (int i = n - 1; i >= 0; i--) {
swap(arr, i, 0);
heapify(arr, i, 0);
}
}
总结
以上的排序算法都是基于比较的排序算法。通过比较来决定元素之间的相对次序，其时间复杂度不能突破O(nlogn)的界限。
关于稳定性，如果一个排序算法能够保留数组中重复元素的相对位置，就是稳定的。怎么记忆呢？不稳定的排序算法可以用”快些选对“谐音来记：快速排序、希尔排序、选择排序、堆排序。
用一张表格来作为小结：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) ~ O(n^2) | O(n1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
高晓松老师曾说：生活不只是眼前的苟且，还有诗和远方。而我希望远方不远，有处可寻，祝大家早日拿到Offer。