Java数据结构（十一）——归并排序、计数排序

文章目录

归并排序
- 算法介绍
- 代码实现
- 非递归实现
- 复杂度和稳定性
计数排序
- 算法介绍
- 代码实现
- 复杂度和稳定性

归并排序

算法介绍

归并排序是一种分而治之的排序算法。基本思想是： 将一个数组分成两半，对每半部分递归地应用归并排序先进行分解，然后将排序好的两半合并在一起。

相比于快速排序，归并排序每次都是从中间位置将序列分解为两个子序列，这使得归并排序不会出现像快速排序那样的最坏时间复杂度。

分解成什么程度开始合并？

当某次递归分解得到的左右子区间都有序时进行合并。

如果归并之前左右子区间无序，怎么办？

我们可以从更小的不能再被分割的子区间（左右区间都是一个元素）开始归并。所以我们可以采用递归的方式来实现这样的一个思路。其思路类似于二叉树的后序遍历。

合并的思路是怎样的？

假设现在有一个数组，该数组的前半部分有序，后半部分有序（模拟归并排序的场景），将它们合并成一个有序的序列，思考在原数组进行合并吗？不行，会出现数据覆盖的情况，所以我们得需要一块额外的空间来将合并后的序列存放在这里，合并完毕后，需要将额外空间中的数据拷贝回原数组。

合并的思路：创建两个指针分别指向两个有序区间的开始位置，然后依次比较取小的放到新的数组里，当一个有序区间的所有元素全部放到新数组里后，再将另外一个有序区间剩下的所有元素放到新数组中。

图示：

在这里插入图片描述

归并排序属于易分难合的排序，上面演示的就是每次合并的思路。整体的归并排序可以使用下图表示：

在这里插入图片描述

代码实现

    public void mergeSort(int[] array, int left, int right) {//分组if(left >= right) {return;}int mid = (left + right) >> 1;mergeSort(array, left, mid);mergeSort(array, mid + 1, right);//合并int[] tmp = new int[right - left + 1];int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = 0;while(begin1 <= end1 && begin2 <= end2) {if(array[begin1] < array[begin2]) {tmp[index++] = array[begin1++];}else {tmp[index++] = array[begin2++];}}while(begin1 <= end1) {tmp[index++] = array[begin1++];}while(begin2 <= end2) {tmp[index++] = array[begin2++];}//拷贝for(int i = 0; i < tmp.length; i++) {array[i+left] = tmp[i];}

注意问题：拷贝时拷回原数组的位置，不一定是从0下标位置开始拷回。

非递归实现

怎么分解、合并？

最开始将每一个元素看作有序序列，即每次将两个元素个数（gap）为1的序列合并，合并后如下：

在这里插入图片描述

第一次合并后，每两个元素是一个元素个数（gap）为2的有序序列，继续合并：

在这里插入图片描述

确定left、mid和right的规律：

在这里插入图片描述

left = i;
mid = left + gap - 1;
right = mid + gap;

以此类推：

在这里插入图片描述

观察上图可以发现：按照上面推导的公式计算left、mid、right，可能会导致 right、mid越界，这需要我们特殊处理，如果还是不理解，可以结合接下来的代码实现理解。

    public void mergeSortNoR(int[] array, int left, int right) {int gap = 1;while(gap < array.length) {for (int i = 0; i < array.length; i = i + 2 * gap) {//创建_left、_mid、_right三个变量方便理解，读者实现时可以优化掉。int _left = i;int _mid = _left + gap - 1;//_mid可能越界if(_mid >= array.length) {_mid = array.length - 1;}int _right = _mid + gap;//_right可能越界if(_right >= array.length) {_right = array.length - 1;}//合并int begin1 = _left;int end1 = _mid;int begin2 = _mid + 1;int end2 = _right;int index = 0;int[] tmp = new int[end2 - begin1 + 1];while(begin1 <= end1 && begin2 <= end2) {if(array[begin1] < array[begin2]) {tmp[index++] = array[begin1++];}else {tmp[index++] = array[begin2++];}}while(begin1 <= end1) {tmp[index++] = array[begin1++];}while(begin2 <= end2) {tmp[index++] = array[begin2++];}//拷贝for(int j = 0; j < tmp.length; j++) {array[j+_left] = tmp[j];}}gap *= 2;}}

注意for循环的i的 变化规则：i = i + 2 * gap，这样就能找到当前gap的下一组合并的开始位置，即left

复杂度和稳定性

时间复杂度：O(N*log2N)

最优情况：O(N*log2N)
平均情况：O(N*log2N)
最差情况：O(N*log2N)

归并排序的时间复杂度在所有情况下都是O(N*log2N)，这是因为它总是将数组分成两半进行递归排序，然后将它们合并。合并操作的时间复杂度是线性的，即O(N)，但由于这个过程需要递归地发生log2N次（因为每次数组大小减半），所以总的时间复杂度是O(N*log2N)。

空间复杂度：O(N)

归并排序在合并过程中需要额外的存储空间来存储临时数组，因此其空间复杂度是O(N)。在最坏的情况下，它需要与原始数组同样大小的额外空间来进行合并操作。

稳定性：稳定

对于归并排序还有一些补充的知识：

归并排序又被称为外排序，表明了归并排序能用来对外存数据排序，如硬盘。一般的电脑的内存大小只有4~8G，如果这时候要对硬盘里的10个G的数据进行排序，我们只能依赖归并排序，假设这时候内存只能使用1G，思路是：

先将10个G的数据分为10块1G的数据，一块一块地置入内存（读文件），利用快速排序将10块1G的数据排好序，写入文件，然后利用归并的思想归并完所有的数据。

为什么这种情况只能使用归并排序？补充一点原因

文件的读和写只能依次进行读写，归并排序满足这样的特点。而快速排序需要分别从头和尾部向中间遍历，这样的思想与读写文件的固有特点相违背。

计数排序

算法介绍

计数排序与之前的排序算法不同，它是一种 非基于比较 的排序算法。它特别适用于待排序元素为整数且范围较小的情况，能够在这些情况下实现高效的排序。以下是计数排序的基本原理：

计数排序通过统计每个元素出现的次数，然后利用这些次数信息将原始序列重新组合成有序序列。具体来说，它首先确定待排序元素的范围，然后创建一个计数数组（或称为桶），该数组的长度等于待排序元素的最大值加1。接下来，遍历待排序数组，统计每个元素出现的次数，并将这些次数存储在计数数组的相应位置上。最后，根据计数数组的信息，依次将元素放回原始数组中的正确位置，完成排序。

在这里插入图片描述

考虑：如果要排序的数组中的元素只出现了例如100、97、78、99这样的较大数，按照上面的思想，计数数组大小为最大值100+1 = 101，此时计数数组中0~77下标位置的空间全部都浪费了，为了减少空间浪费并提高排序效率，将计数数组大小的计算优化为：length = maxVal - minVal + 1。

但这同时意味着优化前的填充计数数组的规则不适用了，新的填充规则为：count[array[i] - minVal]++，具体如下图：

在这里插入图片描述

代码实现

    public void countSort() {//寻找最值，确定范围int minVal = array[0];int maxVal = array[0];for(int i = 1; i < array.length; i++) {if(array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}int[] count = new int[maxVal - minVal + 1];//计数for (int i = 0; i < array.length; i++) {int tmp = array[i];count[tmp - minVal]++;}//填充int index = 0;for(int i = 0; i < count.length; i++) {while(count[i] > 0) {array[index] = i + minVal;index++;count[i]--;}}}