---

目录

1、上期回顾

2、冒泡排序

3、快速排序

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

3.2 Hoare 法

3.3 三数取中

3.4 小区间优化

3.5 挖坑法

3.6 前后指针法

3.7 注意事项

4、归并排序

---

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 还要限制呢

1. 如果左边作为基准值的话只能从右边开始找如果从左边开始找当 begin 和 end 相遇之后的值要比基准值大因为 begin 和 end 交换后end 位置的值已经比基准值要大了
2. 如果不取等于号可能会造成死循环你设想下不取等于号时区间里第一个元素和最后一个元素相同的情况下。
3. 如果这组数本来就是升序的呢右边 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 和 endend 从右找比基准小的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 和 prevcur 起始位置为 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];
    }
}

• 时间复杂度分析O(n*logn)
• 空间复杂度分析最多会开辟数组长度个空间即 O(n)
• 稳定性稳定
• 堆排序主要用于外排序

---

下期预告【Java 数据结构】二叉搜索树