排序算法之——归并排序，计数排序

🕗 发布于 2024-09-30 15:05 排序算法算法 c语言 c++

文章目录

前言
一、归并排序
二、计数排序
总结（排序算法稳定性）

前言

今天我们一起来了解归并排序（MergeSort），以及一种非比较的计数排序（CountSort）~

在这里插入图片描述

一、归并排序

1. 归并排序的思想

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的高效排序算法。它的核心步骤包括将一个数组分割成更小的子数组，对这些子数组进行排序，然后将它们合并成一个有序的数组。以下是归并排序的核心步骤详解：

归并排序的核心步骤：

分割（Divide）：
- 将待排序数组从中间分割成两个子数组（通常是左半部分和右半部分）。
- 继续递归地将这两个子数组再分割，直到每个子数组的大小为 1（即只有一个元素），因为一个元素的数组是有序的。
归并（Merge）：
- 将两个有序的子数组合并成一个有序的数组。
- 使用两个指针分别指向两个子数组的开头，比较指针指向的元素，将较小的元素放入新数组中，并移动相应的指针。
- 当其中一个子数组的元素被全部放入新数组后，将另一个子数组剩余的元素直接复制到新数组的后面。
组合（Combine）：
- 在归并的过程中，逐步形成更大的有序数组，最终得到一个完整的有序数组。

总结：
归并排序是一种高效的排序算法，利用分治法的思想，通过将大问题分解为小问题来解决。其稳定性、时间复杂度 O(n log n) 以及适用于大规模数据的特性使其在实际应用中非常流行。

我们一起来看下面的图：
在这里插入图片描述

通过这张图我们可以很直观的感受到归并排序的分解和合并过程，它的步骤是这样的：

归并排序步骤总结：

定义归并排序主函数：
- MergeSort 函数接受待排序数组和数组的大小作为参数。
- 在函数中分配一个临时数组 tmp，用于辅助合并数组。其实我们合并出来的数据是在tmp中的，最后拷贝回去。
- 调用 _MergeSort 函数进行排序。
```
void MergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(sizeof(int) * n); // 创建临时数组
    _MergeSort(arr, 0, n - 1, tmp); // 调用归并排序
    free(tmp); // 释放临时数组
}
```
定义归并排序递归函数：
- _MergeSort 函数接受数组、左边界、右边界和临时数组作为参数。
- 基本情况：如果 left 大于或等于 right，则返回，表示该子数组已经有序。
```
void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) {
        return; // 基本情况
    }
    ...
}
```
分割数组：
- 计算中间索引 mid，将数组分割为左右两个部分。
- 递归调用 _MergeSort 对左半部分（left 到 mid）和右半部分（mid + 1 到 right）进行排序。
对于它的每一个左右两侧都要继续分割（以左侧为例）：
```
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp); // 递归排序左半部分
_MergeSort(arr, mid + 1, right, tmp); // 递归排序右半部分
```

合并有序子数组：

定义两个指针 begin1 和 begin2，分别指向左子数组和右子数组的起始位置。
使用 index 指针在临时数组 tmp 中进行合并。

在这里插入图片描述

int begin1 = left, end1 = mid; // 左子数组范围
int begin2 = mid + 1, end2 = right; // 右子数组范围
int index = begin1; // 临时数组下标

while (begin1 <= end1 && begin2 <= end2) {
    if (arr[begin1] < arr[begin2]) {
        tmp[index++] = arr[begin1++]; // 复制较小的元素
    } else {
        tmp[index++] = arr[begin2++];
    }
}

处理剩余元素：

如果左子数组还有剩余元素，将其复制到 tmp 中。
如果右子数组还有剩余元素，也将其复制到 tmp 中。

while (begin1 <= end1) {
    tmp[index++] = arr[begin1++]; // 复制左子数组剩余元素
}
while (begin2 <= end2) {
    tmp[index++] = arr[begin2++]; // 复制右子数组剩余元素
}

将合并结果复制回原数组：

将临时数组 tmp 中的有序元素复制回原数组 arr 的相应位置。

for (int i = left; i <= right; i++) {
    arr[i] = tmp[i]; // 将临时数组的内容复制回原数组
}

2. 归并排序时间复杂度及空间复杂度

归并排序（Merge Sort）是一种高效的排序算法，其时间复杂度和空间复杂度如下：

时间复杂度 :

归并排序的时间复杂度为 O(n log n)：
- 分割阶段：每次将数组分成两个子数组，深度为 log n，表示分割的层数。
- 合并阶段：在每一层中，合并两个子数组的过程需要 O(n) 的时间，因为每个元素都要被处理一次。
- 因此，整个算法的时间复杂度可以表示为：
- 根据主定理，得到归并排序的时间复杂度为 O(n log n)。

空间复杂度 :

归并排序的空间复杂度为 O(n)：
- 归并排序需要使用额外的临时数组来存储合并过程中的结果。在每次合并操作中，都会分配一个大小为 n 的临时数组，因此其空间复杂度为 O(n)。

总结：

时间复杂度：O(n log n)
空间复杂度：O(n)

3. 归并排序代码实现

1）递归版本

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}

int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);

int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//index 为tmp下标，不一定是0，而是左边界
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}

while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}

for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}



void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}

2）非递归版本


/*
非递归排序与递归排序相反，将一个元素与相邻元素构成有序数组，
再与旁边数组构成有序数组，直至整个数组有序。
要有mid指针传入，因为不足一组数据时，重新计算mid划分会有问题
需要指定mid的位置
*/
void merge(int* a, int left, int mid, int right, int* tmp)
{
// [left, mid]
// [mid+1, right]
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}

while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}

while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}

memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}

/*
k用来表示每次k个元素归并
*/
void mergePass(int* arr, int k, int n, int* temp)
{
int i = 0;
//从前往后,将2个长度为k的子序列合并为1个
while (i < n - 2 * k + 1)
{
merge(arr, i, i + k - 1, i + 2 * k - 1, temp);
i += 2 * k;
}
//合并区间[i, n - 1]有序的左半部分[i, i + k - 1]以及不及一个步长的右半部分[i + k, n - 1]
if (i < n - k)
{
merge(arr, i, i + k - 1, n - 1, temp);
}

}

二、计数排序

1. 计数排序的思想

计数排序是一种非比较排序算法，适用于范围有限的整数数据。它的核心思想是利用数组的索引来直接计算元素的位置，达到排序的目的。
1）统计相同元素出现次数
2）根据统计的结果将序列回收到原来的序列

我们来看下面这张图：
在这里插入图片描述
这是我们待排序的数组。

第一步：定义一个新数组，使得旧数组的元素值是新数组的下标

假设，我们定义成这样行不行？

如果完全按照旧数组的元素值来开空间会造成大量的空间浪费，因此不可取。

这里还有一个问题，如果旧数组的元素值是负数怎么办呢？

这里空间问题可以和负数问题一起解决：

首先找到旧数组的最小值，以及最大值
在这里插入图片描述

遍历一遍数组很容易找到数组最小值为100，最大值为109.

那我们开的空间 range 就是最值差
在这里插入图片描述

第二步：旧数组中每一个元素减去最小值min作为新数组下标，出现了几个新数组对应的下标中的元素就是多少，这样也顺便解决了负数问题，因为负数 - 更小的负数 = 正数。

在这里插入图片描述

第三步：遍历新数组，只要数组数据不为零就循环次数（数组值），输出内容（i + min），将所有元素拷贝回原来的数组，就完成了排序。

2. 计数排序的时间复杂度及空间复杂度

计数排序是一种有效的排序算法，特别适用于数据范围有限的情况。根据你提供的代码，以下是计数排序的时间复杂度和空间复杂度分析：

时间复杂度：

计数排序的时间复杂度为 O(n + k)，其中：

n：待排序数组的大小。
k：待排序元素的范围（最大值 - 最小值 + 1）。

分析过程：

找最大最小值：遍历数组一次，找到最大值和最小值，时间复杂度为 O(n)。
创建计数数组：分配大小为 k 的计数数组，时间复杂度为 O(k)。
统计元素出现次数：再次遍历原数组，将每个元素的出现次数记录在计数数组中，时间复杂度为 O(n)。
放回排序结果：遍历计数数组，根据记录的次数将元素放回原数组，最坏情况下需要遍历 k 次，时间复杂度为 O(k)。

因此，总的时间复杂度为：
在这里插入图片描述

空间复杂度：

计数排序的空间复杂度为 O(k)，其中 k 是待排序元素的范围。

分析过程：

需要一个计数数组 count，其大小为 k，用于存储每个元素出现的次数。
如果输出数组与原数组相同，空间复杂度会增加到 O(n + k)（包含原数组和计数数组），但通常我们只考虑额外空间，因此空间复杂度通常记为 O(k)。

总结

时间复杂度：O(n + k)
空间复杂度：O(k)

这种复杂度特性使得计数排序在处理范围有限的整数数据时非常高效。适合用于大规模的正整数排序，尤其在数值分布相对均匀的情况下。
但缺点也很明显，数据过于分散太浪费空间，而且只能处理整数数据！

3. 计数排序代码实现

// 计数排序
void CountSort(int* arr, int n)
{
int max = arr[0], min = arr[0];

//找最大最小值
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}

//定义新数组空间大小
int range = max - min + 1;

int* count = (int*)malloc(range * sizeof(int));
if (count == NULL)
{
perror("malloc fail!");
exit(1);
}

//初始化range数组中所有的数据为0
memset(count, 0, sizeof(int) * range);

//原来的下标成为元素，原来的(元素 - min) 成为下标，出现几次新的元素就加几次
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}

//把排好序的元素放回原数组
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
}

总结（排序算法稳定性）

到了这里我们所有排序思想已经学完了，再来一起总结一下吧！

排序算法复杂度及稳定性分析：

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的
相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之
前，则称这种排序算法是稳定的；否则称为不稳定的。

在这里插入图片描述

谢谢大家~

在这里插入图片描述

原文地址：https://blog.csdn.net/Jdxxwu/article/details/142622986

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：腾讯二面：40亿QQ号, 1G内存，怎么去重？
下一篇：【综合性渗透利器】- TscanPlus

vue3 + element-plus 的 upload + axios + django 文件上传并保存
之前在网上搜了好多教程，一直没有找到合适自己的，要么只有前端部分没有后端，要么就是写的不是很明白。所以还得靠自己摸索出来后，来此记录一下整个过程。环境安装什么的就不讲了，直接上代码好吧，这个是样式图。
阅读更多2024-11-06
Cuebric：用AI重新定义3D创作的未来
Cuebric 是一家成立于2022年夏天的好莱坞创新公司，致力于为电影、电视、游戏和时尚等行业提供先进的AI多模态SaaS平台。自2024年1月正式推出以来，Cuebric 已经在市场上获得了广泛的
阅读更多2024-11-06
easyui+vue 数据表更新问题的解决
数据的增删改查可以实时刷新出来,不建议在封装组件。nextTick 保证DOM 渲染完成。
阅读更多2024-11-06
软件测试基础：单元测试与集成测试
单元测试和集成测试是软件测试的基础，它们的重要性不言而喻。通过对软件的不同部分进行有序的测试，可以提高软件质量、减少后期维护成本，保证软件的可靠性和稳定性。软件开发者和测试人员应当重视并深入理解单元测
阅读更多2024-11-06
RxJS基本介绍以及与Promise的区别
Promise 适合处理单一的异步操作，具有更简单的 API，但缺乏灵活性和对多值的支持。RxJS (Observable) 适合处理复杂的异步流和多事件流，具有更多的操作符、错误处理机制和强大的组合
阅读更多2024-11-06
第三节 Vim编辑器与Shell命令脚本
这里的脚本主要使用 ping 命令来测试与对方主机的网络连通性，而 Linux 系统中的 ping 命令不像 Windows 一样尝试 4 次就结束，因此为了避免用户等待时间过长，需要通过-c 参数来
阅读更多2024-11-06
【JavaEE初阶 — 多线程】线程安全问题＆ synchronized
【JavaEE初阶 — 多线程】线程安全问题＆ Synchronized观察线程安全问题，分析了造成线程安全问题造成的三个原因：线程的随机调度，多个线程修改共享数据（修改同一个变量），以及原子性问题
阅读更多2024-11-06
十月末补充（？
【代码】十月末补充（？
阅读更多2024-11-06
13-鸿蒙开发中的综合实战：华为登录界面
通过本文，你已经学会了如何在鸿蒙开发中实现一个简单的登录界面，涵盖了输入框组件、按钮组件、文本组件和布局容器的使用。这个实战项目不仅帮助你巩固了基础知识，还提供了一个实际的应用场景。希望这篇文章对你有
阅读更多2024-11-06
python全栈开发《59.集合的增删改》
目录1.集合的add函数2.集合的update函数3.集合的remove函数4.集合的clear函数5.用del删除集合6.重要说明7.代码1.集合的add函数1.1add的功能用于集合中添加一个元素
阅读更多2024-11-06

排序算法之——归并排序，计数排序

文章目录

前言

一、归并排序

1. 归并排序的思想

2. 归并排序时间复杂度及空间复杂度

3. 归并排序代码实现

1）递归版本

2）非递归版本

二、计数排序

1. 计数排序的思想

2. 计数排序的时间复杂度及空间复杂度

3. 计数排序代码实现

总结（排序算法稳定性）

相关文章