【Java 数据结构】常见排序算法(下)

1、上期回顾

上期我们主要介绍了排序的基本认识，以及四个排序，分别是直接插入排序，希尔排序，选择排序，堆排序，从这些排序中，了解了算法的实现，以及复杂度，和排序稳定性的相关知识，本期我们将继续讲解剩下的排序内容。注：后续所说的复杂度 log，都是以2为底，特殊的会标注出来。

2、冒泡排序

这个排序肯定是见多不怪了，我记得我在学校学习C语言的阶段，第一个接触的排序就是冒泡排序，它本身也是个很简单的排序，这里就直接上代码了：

public void bubbleSort(int[] array) {    // 外循环控制比较的趟数    for (int i = 0; i < array.length - 1; i++) {        boolean flag = true;        // 内循环控制需要比较的元素个数        for (int j = 0; j < array.length - 1 - i; j++) {            if (array[j] > array[j + 1]) {                swap(array, j, j + 1);                flag = false;            }        }        if (flag) {            return;        }    }}

不过这里我们需要注意，此处采用的 flag 是对该排序做的一种优化，如果当进入内循环之后，发现没有发生交换，则表示此时的数据已经有序了，不需要接着去比较了。

时间复杂度分析：这个排序就很简单了，O(n^2)
空间复杂度分析：O(1)
稳定性：稳定

3、快速排序

这个排序算是我们比较重要的一个排序了，快速排序是Hoare在1962年提出的一种二叉树结构的交换排序法，如果你还没有接触过二叉树相关的知识，可以转至博主的二叉树文章中学习学习。

3.1 理解快速排序的二叉树结构

如何理解快速排序的二叉树结构呢？可以这样来想象一下：

你面前有一组数字，令第一个数作为基准值，你需要将这个基准值放到某个位置上，满足基准值的左边都比这个基准值小，右边都比基准值大，因此由基准值为界限又被划为了左右两个区间，这两个区间再次重复上述的操作。这样一来就可以看作一棵二叉树！

而如何确定基准值的位置，这就是我们快速排序要实现的算法！本期我们一共会讲解三种版本，方便大家学习快速排序。下面我们就用一张图，来描述下上述我们所说的理论部分。

这里先不关心博主画图用的是哪种版本的方法，主要来验证下我们上面所说的，每个区间所找的基准值，最终放到固定位置之后，基准值的左边比它小，基准值的右边比它大。最终我们来从左往右看上图，其实就排序成功了。当然光看图可能了解的不是很通透，那么下面，我们结合着这张图，来实现快速排序的三种算法。

为了实参传递的统一性，我们快速排序的形参统一为以下格式，调用被封装的 quick 方法：

public void quickSort(int[] array) {    quick(array, 0, array.length - 1);}

3.2 Hoare 法

我上面画的那幅图就是 Hoare 法，主要逻辑是，令区间第一个数为基准值，定义两个变量，分别表示区间左边起始位置下标，和右边起始位置下标(区间最后一个数的下标)，先从右边开始找比基准值小的，再去左边找比基准值大的，找到之后，交换这两个值，当这两个下标相遇了，就把基准值与其中一个下标交换即可，这样就能达到，基准值的左边都比它小，右边都比它大。

代码如下：

private void quick(int[] array, int left, int right) {    if (left >= right) {        return;    }    int pivot = partitionHoare(array, left, right);    quick(array, left, pivot - 1); //左区间    quick(array, pivot + 1, right); //右区间}private int partitionHoare(int[] array, int left, int right) {    int pivot = array[left]; //将该区间第一个数作为基准值    int begin = left;    int end = right;    while (begin < end) {        // 右边找比基准小的数的下标, 为什么要取 >= 呢？        while (begin < end && array[end] >= pivot) {            end--;        }        // 左边找比基准大的数的下标        while (begin < end && array[begin] <= pivot) {            begin++;        }        // 交换        swap(array, begin, end);    }    swap(array, left, begin);    return begin; //返回基准值当前所处的下标, 左边都比它小, 右边都比它大}

单看 quick 方法，有点像二叉树的前序遍历，确实也是这样的，前面我们也说过，快排是一种二叉树的结构，结合着代码再去看那幅图，是不是理解的更通透了呢？

这里有两个问题，我们来看 partitionHoare 方法实现里面：

1. 为什么要从右边开始找？

2. 为什么要取等于号，直接 > 或 < 不可以吗？

3. 外面的循环不是限制了 begin < end 吗？为什么里面的 while 还要限制呢？

如果左边作为基准值的话，只能从右边开始找，如果从左边开始找，当 begin 和 end 相遇之后的值，要比基准值大，因为 begin 和 end 交换后，end 位置的值已经比基准值要大了
如果不取等于号，可能会造成死循环，你设想下不取等于号时，区间里第一个元素和最后一个元素相同的情况下。
如果这组数本来就是升序的呢？右边 end 找不到比基准值小的数，如果基准就是最小的数呢？内部 whild 不限制的话 end 是不是会自减成为负数？导致下标不合法了？

上面这三点或许是小伙伴们有疑问的地方，这里给大家伙解释一下，那么再来思考个问题，什么情况下快速排序的效率最低呢？

当数组有序的情况下，快速排序的时间效率最差！试想一下，如果每次找的基准值都是最小的话，划分区间的时候，是不是就成了一棵没有左树的二叉树了啊？类似于一种链表的结构了，见下图：

为了解决这种极端情况下，快速排序划分不均匀的问题，于是便有了三数取中的算法，这算是对快速排序的一种优化，三数取中到底是啥，请接着往后看：

3.3 三数取中

三数取中，是针对快速排序极端情况下，为了均匀的分割区间而采用的一种优化，其步骤是，取该区间的第一个值，最后一个值，以及该区间中间位置的值，求出这三个值中第二大的数，与第一个值交换，这样一来，只要基准值不是最小的，就一定程度上能使区间分割的更均匀。

简单来说，就是有三个数的下标，让你求出第二大的值的下标嘛，这个还是比较简单的，我就直接来放代码了：

private int findMidValOfIndex(int[] array, int left, int right) {    int mid = (left + right) >> 1;    if (array[left] < array[right]) {        if (array[left] < array[mid]) {            // 走到这里面, left位置一定是最小的值            // 我们这里只需要判断 mid 和 right 哪个位置小即可            if (array[mid] < array[right]) {                //mid是第二大的值                return mid;            } else {                return right;            }        } else {            // 走到这里, 则left位置小于等于right位置, 并大于mid位置, 则left是第二大的值            return left;        }    } else { // 走这个else表示left位置大于等于right位置        if (array[left] > array[mid]) {            // 走到这里表示 left 位置一定是最大的值,            // 我们只需要判断 mid 和 right 位置哪个大即可            if (array[mid] > array[right]) {                return mid;            } else  {                return right;            }        } else {            //走到这表示 left位置大于right位置, 并小于等于mid位置, 则left是第二大的值            return left;        }    }}

这样的话，在我们 quick 方法中，求到了第二大值下标后，与 left 位置交换下即可：

private void quick(int[] array, int left, int right) {    if (left >= right) {        return;    }    // 三数取中    int mid = findMidValOfIndex(array, left, right);    swap(array, left, mid);    int pivot = partitionHoare(array, left, right);    quick(array, left, pivot - 1);    quick(array, pivot + 1, right);}

那这样一来，我们上面的效率最低的例子是不是就可以得到改善了？但是这样优化还是不够，因为当我们数据量够大的时候，二叉树的层数就越高，而越往后，区间被分割的越小，里面的数据也就越接近有序，但是越接近有序了，还会往下分割，这样会造成大量的压栈操作，递归本身就是在压栈的过程嘛，为了减少这样的情况，又有一个优化办法：小区间优化。

3.4 小区间优化

数据量大的时候，分割到区间越小，则表示数据越接近有序了，前面我们认识了一个数据越接近有序效率越快的排序，那就是直接插入排序，所以我们可以进行小区间优化，那么简单来说，就是当区间的数据个数小于某个值的时候，采用直接插入排序算法。

private void quick(int[] array, int left, int right) {    if (left >= right) {        return;    }    // 小区间优化 -> 如果待排序的数据小于15个,我们直接使用直接插入排序    if ((right - left + 1) < 15) {        insertSort(array);        return;    }    // 三数取中    int mid = findMidValOfIndex(array, left, right);    swap(array, left, mid);    int pivot = partitionHoare(array, left, right);    quick(array, left, pivot - 1);    quick(array, pivot + 1, right);}

时间复杂度分析：在我们有了三数取中优化的情况下，可以达到 O(n*logn)，如果没有三数取中，极端最坏的情况下，能达到 O(n^2)，但是我们通常说的快排都是优化过的，也就是 O(n*logn)。
空间复杂度分析：每次递归都会压栈，随之开辟空间，那么快排类似于二叉树的前序遍历，左子树遍历完了，再有右子树，也就是会压栈，也会出栈，那么最大压栈多少呢？显然是树的高度，即 O(logn)。
稳定性：不稳定
快速排序整体的综合性能和使用场景都是比较好的

到这，快速排序基本上就实现完成了，但是还有两个版本，我们接着往后看。

3.5 挖坑法

这个方法很简单，主要思路就是，一样有两个引用，begin 和 end，end 从右找比基准小的，begin从左找比基准大的，当 end 找到比基准小的，直接覆盖掉 begin 的位置，接着 begin 找到了比基准大的接着去覆盖 end 位置，相遇后，将基准值覆盖掉 begin 和 end 任意一个位置即可。直接看代码：

private int partitionPivot(int[] array, int left, int right) {    int pivot = array[left];    int begin = left;    int end = right;    while (begin < end) {        while (begin < end && array[end] >= pivot) {            end--;        }        array[begin] = array[end];        while (begin < end && array[begin] <= pivot) {            begin++;        }        array[end] = array[begin];    }    array[begin] = pivot;    return begin;}

我们平时所见到的快速排序，大多数都是挖坑法居多。

3.6 前后指针法

这个算法用的很少很少，思路就是，定义一个 cur 和 prev，cur 起始位置为 left+1，只要 cur 不大于 right，就往前走，找到比基准小的值就停下来，与 ++prev 位置的值进行交换，这样一来，比基准小的值跑到前面来了，cur 走完了之后，再把基准值与 prev 位置的值交换，也就满足了基准值左边比它小，右边比它大。

private int partitionPointer(int[] array, int left, int right) {    int prev = left;    int cur = left + 1;    while (cur <= right) {        // && 后面的避免自己跟自己交换        if (array[cur] < array[left] && ++prev != cur) {            swap(array, prev, cur);        }        cur++;    }    swap(array, left, prev);    return prev;}

3.7 注意事项

这三种方法，每种方法第一次分割后的结果可能都不相同，所以未来如果碰到类似让你求快排第一次分割后结果的序列，优先考虑挖坑法，再Hoare法，最后考虑前后指针法。

但是博主还是希望看到这篇文章的小伙伴，能把这三种版本都掌握，不怕学的多，就怕你不学。

4、归并排序

这个排序如何去想象呢，就类似于，你拿到一组数的时候，从中间砍一刀，变成了两个区间，接着把这两个区间分别再砍一刀，变成了四个区间，一直重复下去，当区间的元素个数砍成了一个的时候，那么这个区间就有序了，接着我们开始进行二路归并，也就是说把两个有序区间，合并成一个有序区间，这样一来，是不是整体就有序了？我们看图：

归并排序也需要对递归有一定的学习，按照上图来看，我们肯定是要先递归到每个区间只有一个元素的时候才能进行归并的，归并的逻辑就是，将两个有序序列合并成一个有序序列嘛，这还是蛮简单的，我们来看代码：

public void mergeSort(int[] array) {    mergeSortChild(array, 0, array.length - 1);}private void mergeSortChild(int[] array, int left, int right) {    if (left >= right) {        return;    }     int mid = (left + right) >> 1;    mergeSortChild(array, left, mid);    mergeSortChild(array, mid + 1, right);    merge(array, left, mid, right);}private void merge(int[] array, int left, int mid, int right) {    // 准备归并 -> 将传过来的两个有序区间, 合并成一个有序区间    int begin1 = left;    int end1 = mid;    int begin2 = mid + 1;    int end2 = right;    int[] tmp = new int[right - left + 1];    int k = 0;    while (begin1 <= end1 && begin2 <= end2) {        if (array[begin1] < array[begin2]) {            tmp[k++] = array[begin1++];        } else {            tmp[k++] = array[begin2++];        }    }    // 跳出循环之后, begin1 和 begin2 区间总有一个区间还有剩余的元素未拷贝进tmp    while (begin1 <= end1) {        tmp[k++] = array[begin1++];    }    while (begin2 <= end2) {        tmp[k++] = array[begin2++];    }    // 将tmp的数据拷回array中    for (int i = 0; i < k; i++) {        array[i + left] = tmp[i];    }}