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

文章目录

  • 前言
  • 一、归并排序
    • 1. 归并排序的思想
    • 2. 归并排序时间复杂度及空间复杂度
    • 3. 归并排序代码实现
      • 1）递归版本
      • 2）非递归版本
  • 二、计数排序
    • 1. 计数排序的思想
    • 2. 计数排序的时间复杂度及空间复杂度
    • 3. 计数排序代码实现
  • 总结（排序算法稳定性）

前言

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

在这里插入图片描述

一、归并排序

1. 归并排序的思想

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

归并排序的核心步骤：

  1. 分割（Divide）：

    • 将待排序数组从中间分割成两个子数组（通常是左半部分和右半部分）。
    • 继续递归地将这两个子数组再分割，直到每个子数组的大小为 1（即只有一个元素），因为一个元素的数组是有序的。

  2. 归并（Merge）：

    • 将两个有序的子数组合并成一个有序的数组。
    • 使用两个指针分别指向两个子数组的开头，比较指针指向的元素，将较小的元素放入新数组中，并移动相应的指针。
    • 当其中一个子数组的元素被全部放入新数组后，将另一个子数组剩余的元素直接复制到新数组的后面。

  3. 组合（Combine）：

    • 在归并的过程中，逐步形成更大的有序数组，最终得到一个完整的有序数组。

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

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

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

归并排序步骤总结 ：

  1. 定义归并排序主函数：

    • 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); // 释放临时数组
}

  2. 定义归并排序递归函数：

    • _MergeSort 函数接受数组、左边界、右边界和临时数组作为参数。
    • 基本情况：如果 left 大于或等于 right，则返回，表示该子数组已经有序。
    void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) {
        return; // 基本情况
    }
    ...
}

  3. 分割数组：

    • 计算中间索引 mid，将数组分割为左右两个部分。
    • 递归调用 _MergeSort 对左半部分（left 到 mid）和右半部分（mid + 1 到 right）进行排序。

    在这里插入图片描述
    对于它的每一个左右两侧都要继续分割（以左侧为例）：
    在这里插入图片描述

    int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp); // 递归排序左半部分
_MergeSort(arr, mid + 1, right, tmp); // 递归排序右半部分

  4. 合并有序子数组：

    • 定义两个指针 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++];
    }
}

  5. 处理剩余元素：

    • 如果左子数组还有剩余元素，将其复制到 tmp 中。
    • 如果右子数组还有剩余元素，也将其复制到 tmp 中。
    while (begin1 <= end1) {
    tmp[index++] = arr[begin1++]; // 复制左子数组剩余元素
}
while (begin2 <= end2) {
    tmp[index++] = arr[begin2++]; // 复制右子数组剩余元素
}

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

    • 将临时数组 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）。

分析过程：

  1. 找最大最小值：遍历数组一次，找到最大值和最小值，时间复杂度为 O(n)。
  2. 创建计数数组：分配大小为 k 的计数数组，时间复杂度为 O(k)。
  3. 统计元素出现次数：再次遍历原数组，将每个元素的出现次数记录在计数数组中，时间复杂度为 O(n)。
  4. 放回排序结果：遍历计数数组，根据记录的次数将元素放回原数组，最坏情况下需要遍历 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]之
前，则称这种排序算法是稳定的；否则称为不稳定的。

在这里插入图片描述

在这里插入图片描述

谢谢大家~

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/886621.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ATLAS/ICESat-2 L3B 每 3 个月网格动态海洋地形图 V001

ATLAS/ICESat-2 L3B 每 3 个月网格动态海洋地形图 V001

目录 简介 摘要 代码 引用 网址推荐 0代码在线构建地图应用 机器学习 ATLAS/ICESat-2 L3B Monthly 3-Month Gridded Dynamic Ocean Topography V001 ATLAS/ICESat-2 L3B 每月 3 个月网格动态海洋地形图 V001 简介 该数据集包含中纬度、北极和南极网格上动态海洋地形&…
阅读更多...
基于大数据的Python+Django电影票房数据可视化分析系统设计与实现

基于大数据的Python+Django电影票房数据可视化分析系统设计与实现

目录 1 引言 2 系统需求分析 3 技术选型 4 系统架构设计 5 关键技术实现 6 系统实现 7 总结与展望 1 引言 随着数字媒体技术的发展&#xff0c;电影产业已经成为全球经济文化不可或缺的一部分。电影不仅是艺术表达的形式&#xff0c;更是大众娱乐的重要来源。在这个背景…
阅读更多...
C++之多线程

C++之多线程

前言 多线程和多进程是并发编程的两个核心概念，它们在现代计算中都非常重要，尤其是在需要处理大量数据、提高程序性能和响应能力的场景中。 多线程的重要性： 资源利用率：多线程可以在单个进程中同时执行多个任务，这可以更有效地利用CPU资源，特别是在多核处理器上。 性…
阅读更多...
【Spring基础3】- Spring的入门程序

【Spring基础3】- Spring的入门程序

目录 3-1 Spring的下载3-2 Spring的 jar 包3-3 第一个 Spring程序第一步&#xff1a;添加spring context的依赖&#xff0c;pom.xml配置如下第二步&#xff1a;添加junit依赖第三步&#xff1a;定义bean&#xff1a;User第四步&#xff1a;编写spring的配置文件&#xff1a;bea…
阅读更多...
macOS终端配置自动补全功能

macOS终端配置自动补全功能

如何在macOS终端中配置自动补全功能 终端是一个非常强大的工具&#xff0c;它可以用来完成很多任务&#xff0c;比如创建、复制、移动、删除文件&#xff0c;执行脚本和运行程序。不过它的默认设置对用户不太友好&#xff0c;作为开发者&#xff0c;我们通常习惯代码编辑器的辅…
阅读更多...
docker pull 超时Timeout失败的解决办法

docker pull 超时Timeout失败的解决办法

当国内开发者docker pull遇到如下提示时&#xff0c;不要惊讶 [rootvm /]# docker pull postgres Using default tag: latest Error response from daemon: Get "https://registry-1.docker.io/v2/": dial tcp 128.121.146.235:443: i/o timeout [rootvm /]# 自2024…
阅读更多...
创建Vue项目的时出现：无法加载文件 E:\software\node\node_global\vue.ps1，因为在此系统上禁止运行脚本

创建Vue项目的时出现：无法加载文件 E:\software\node\node_global\vue.ps1，因为在此系统上禁止运行脚本

创建Vue项目的时出现的问题:出现&#xff1a;无法加载文件 E:\software\node\node_global\vue.ps1&#xff0c;因为在此系统上禁止运行脚本 解决方法&#xff1a; .PowerShelll的执行政策阻止了该操作,用 get-ExecutionPolicy 查看执行策略的状态为受限 输入Set-ExecutionPo…
阅读更多...
T10：数据增强

T10：数据增强

T10周&#xff1a;数据增强 **一、前期工作**1.设置GPU,导入库2.加载数据 **二、数据增强****三、增强方式**方法一&#xff1a;将其嵌入model中方法二&#xff1a;在Dataset数据集中进行数据增强 **四、训练模型****五、自定义增强函数****六、总结** &#x1f368; 本文为&am…
阅读更多...
[ RK3566-Android11 ] 关于移植 RK628F 驱动以及后HDMI-IN图像延迟/无声等问题

[ RK3566-Android11 ] 关于移植 RK628F 驱动以及后HDMI-IN图像延迟/无声等问题

问题描述 由前一篇文章https://blog.csdn.net/jay547063443/article/details/142059700?fromshareblogdetail&sharetypeblogdetail&sharerId142059700&sharereferPC&sharesourcejay547063443&sharefromfrom_link&#xff0c;移植HDMI-IN部分驱动后出现&a…
阅读更多...
硬件-开关电源-结构组成及元件作用

硬件-开关电源-结构组成及元件作用

文章目录 一&#xff1a;开关电源组成1.1 开关电源是什么&#xff1f;1.2 开关电源六个组成部分 二&#xff1a;六个组成部分的作用2.1 EMC区域2.2 输入整流滤波区域2.3 控制区域2.4 变压器2.5 输出整流滤波区域2.6 反馈电路区域道友:勿以小恶弃人大美&#xff0c;勿以小怨忘人…
阅读更多...
【C++】——list的介绍和模拟实现

【C++】——list的介绍和模拟实现

P. S.&#xff1a;以下代码均在VS2019环境下测试&#xff0c;不代表所有编译器均可通过。 P. S.&#xff1a;测试代码均未展示头文件stdio.h的声明&#xff0c;使用时请自行添加。 博主主页&#xff1a;Yan. yan.                        …
阅读更多...
ARM 架构、cpu

ARM 架构、cpu

一、ARM的架构 ARM是一种基于精简指令集&#xff08;RISC&#xff09;的处理器架构. 1、ARM芯片特点 ARM芯片的主要特点有以下几点&#xff1a; 精简指令集&#xff1a;ARM芯片使用精简指令集&#xff0c;即每条指令只完成一项简单的操作&#xff0c;从而提高指令的执行效率…
阅读更多...
EasyCVR视频汇聚平台：解锁视频监控核心功能，打造高效安全监管体系

EasyCVR视频汇聚平台：解锁视频监控核心功能，打造高效安全监管体系

随着科技的飞速发展&#xff0c;视频监控技术已成为现代社会安全、企业管理、智慧城市构建等领域不可或缺的一部分。EasyCVR视频汇聚平台作为一款高性能的视频综合管理平台&#xff0c;凭借其强大的视频处理、汇聚与融合能力&#xff0c;在构建智慧安防/视频监控系统中展现出了…
阅读更多...
Qt Quick 3D 入门：QML 3D场景详解

Qt Quick 3D 入门：QML 3D场景详解

随着 Qt 6 的发布&#xff0c;QtQuick3D 模块带来了新的 3D 渲染和交互能力&#xff0c;使得在 Qt 中创建 3D 场景变得更加简单和直观。本文将带您从一个简单的 QML 3D 应用开始&#xff0c;详细讲解各个相关领域的概念、代码实现以及功能特点。 什么是 Qt Quick 3D&#xff1…
阅读更多...
关于 JVM 个人 NOTE

关于 JVM 个人 NOTE

目录 1、JVM 的体系结构 2、双亲委派机制 3、堆内存调优 4、关于GC垃圾回收机制 4.1 GC中的复制算法 4.2 GC中的标记清除算法 1、JVM 的体系结构 "堆"中存在垃圾而"栈"中不存在垃圾的原因： 堆（Heap） 用途：堆主要用于存储对象实例和数组。在Java中…
阅读更多...
Linux --入门学习笔记

Linux --入门学习笔记

文章目录 Linux概述基础篇Linux 的安装教程 ⇒ 太简单了&#xff0c;百度一搜一大堆。此处略……Linux 的目录结构常用的连接 linux 的开源软件vi 和 vim 编辑器Linux 的关机、开机、重启用户登录和注销用户管理添加用户 ⇒ ( useradd 用户名 ) &#xff08; useradd -d 制定目…
阅读更多...
【Unity踩坑】Unity更新Google Play结算库

【Unity踩坑】Unity更新Google Play结算库

一、问题描述&#xff1a; 在Google Play上提交了app bundle后&#xff0c;提示如下错误。 我使用的是Unity 2022.01.20f1&#xff0c;看来用的Play结算库版本是4.0 查了一下文档&#xff0c;Google Play结算库的维护周期是两年。现在需要更新到至少6.0。 二、更新过程 1. 下…
阅读更多...
Python | Leetcode Python题解之第454题四数相加II

Python | Leetcode Python题解之第454题四数相加II

题目&#xff1a; 题解&#xff1a; class Solution:def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:countAB collections.Counter(u v for u in A for v in B)ans 0for u in C:for v in D:if -u - v in countAB:ans countAB…
阅读更多...
C++ | Leetcode C++题解之第454题四数相加II

C++ | Leetcode C++题解之第454题四数相加II

题目&#xff1a; 题解&#xff1a; class Solution { public:int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> countAB;for (int u: A) {for (int v: B) {count…
阅读更多...
Python并发编程(1)——Python并发编程的几种实现方式

Python并发编程(1)——Python并发编程的几种实现方式

更多精彩内容&#xff0c;请关注同名公众&#xff1a;一点sir&#xff08;alittle-sir&#xff09; Python 并发编程是指在 Python 中编写能够同时执行多个任务的程序。并发编程在任何一门语言当中都是比较难的&#xff0c;因为会涉及各种各样的问题&#xff0c;在Python当中也…
阅读更多...
最新文章

Copyright @ 2022~2023