[C][数据结构][排序][下][快速排序][归并排序]详细讲解

文章目录

  • 1.快速排序
    • 1.基本思想
    • 2.hoare版本
    • 3.挖坑法
    • 4.前后指针版本
    • 5.非递归版本改写
  • 2.归并排序

1.快速排序

1.基本思想

  • 任取待排序元素序列的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

2.hoare版本

请添加图片描述

  • 选key – 一般是最左边或者最右边的值
    • 左作key，让右边先走
    • 右作key，让左边先走
  • 为什么左边做key，要让右边先走?
    • 要保证相遇位置的值，比key小/就是key
      • R先走，R停下，L去遇到R
        • 相遇位置就是R停下来的位置，必定比key小
      • R先走，R没有找到比key小的值，R去遇到了L
        • 相遇位置就是L上一轮停下来的位置，比key小/就是key
  • left向前找大
  • right向后找小
  • 单趟排完以后：
    • 左边都比key小
    • 右边都比key大
  • 实现：
    void QuickSort1(int* a, int begin, int end)
{
	//结束条件  --  只有一个数 --> begin == end || 区间不存在 --> begin > end
	if (begin >= end)
	{
		return;
	}
 
	if (end - begin > 0)
	{
		//hoare版本
		int left = begin, right = end;
		int keyi = left;
 
		while (left < right)
		{
			//右边先走，找小
			while (left < right && a[right] >= a[keyi])  //left < right是为了防止越界
			{
				right--;
			}
 
			//左边再走，找大
			while (left < right && a[left] <= a[keyi])
			{
				left++;
			}
 
			//交换
			Swap(&a[left], &a[right]);
		}
 
		Swap(&a[keyi], &a[left]);
		keyi = left;
 
		//key已经正确的位置上，左边都比key小，右边都比key大
		//递归，分治 --  [begin,keyi - 1]  keyi  [keyi + 1,end]
		QuickSort1(a, begin, keyi - 1);
		QuickSort1(a, keyi + 1, end);
	}
	else
	{
		//直接插入排序
		InsertSort(a + begin, end - begin + 1);
	}
}

3.挖坑法

请添加图片描述

  • 本质同hoare，但是好理解些
  • 右边找小，填到左边的坑里去，这个位置形成新的坑
  • 左边找大，填到右边的坑里去，这个位置形成新的坑
  • 实现：
    void QuickSort2(int* a, int begin, int end)
{
	//结束条件  --  只有一个数 --> begin == end || 区间不存在 --> begin > end
	if (begin >= end)
	{
		return;
	}
 
	if (end - begin > 0)
	{
		//挖坑法
		int key = a[begin];
		int piti = begin;
		int left = begin, right = end;
 
		while (begin < end)
		{
			//右边找小，填到左边的坑里去，这个位置形成新的坑
			while (begin < end && a[right] >= key)
			{
				right--;
			}
 
			a[piti] = a[right];
			piti = right;
 
			//左边找大，填到右边的坑里去，这个位置形成新的坑
			while (begin < end && a[left] <= key)
			{
				left++;
			}
 
			a[piti] = a[left];
			piti = left;
		}
 
		a[piti] = key;
 
		//key已经正确的位置上，左边都比key小，右边都比key大
		//递归，分治 --  [begin,keyi - 1]  keyi  [keyi + 1,end]
		QuickSort2(a, begin, piti - 1);
		QuickSort2(a, piti + 1, end);
	}
	else
	{
		//直接插入排序
		InsertSort(a + begin, end - begin + 1);
	}
}

4.前后指针版本

请添加图片描述

  • cur向前找小，遇到小，则prev++，且交换cur、prev
  • 实现：
    void QuickSort3(int* a, int begin, int end)
{
	//结束条件  --  只有一个数 --> begin == end || 区间不存在 --> begin > end
	if (begin >= end)
	{
		return;
	}
 
	if (end - begin > 0)
	{
		//前后指针版本
		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;
 
		//加入三数取中的优化
		int midi = GetMidIndex(a, begin, end);
		Swap(&a[keyi], &a[midi]);
 
		while (cur <= end)  //一直往后走，遇到小则停下来处理
		{
			//cur找小
			if (a[cur] < a[keyi] && ++prev != cur)  //防止prev和cur重合时，重复交换
			{
				Swap(&a[prev], &a[cur]);
			}
 
			cur++;
		}
 
		Swap(&a[keyi], &a[prev]);
		keyi = prev;
 
		//key已经正确的位置上，左边都比key小，右边都比key大
		//递归，分治 --  [begin,keyi - 1]  keyi  [keyi + 1,end]
		QuickSort3(a, begin, keyi - 1);
		QuickSort3(a, keyi + 1, end);
	}
	else
	{
		//直接插入排序
		InsertSort(a + begin, end - begin + 1);
	}
}

5.非递归版本改写

  • 为何需要改写非递归?
    • 极端场景下，若深度太深，会出现栈溢出
  • 方法：用数据结构栈模拟递归过程
  • 实现：
    //用栈模拟递归 -- 先进后出
void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	
	StackPush(&st, end);
	StackPush(&st, begin);
 
	while (!isStackEmpty(&st))
	{
		//从栈中取出两个数，作为区间
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
 
		//排序，取keyi
		int keyi = PartSort3(a, left, right);
 
		//此时分成了两个区间 [left, keyi-1] keyi [keyi+1, right]
		//继续压栈
		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
 
		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}
 
	StackDestroy(&st);
}
  • 特性总结：
    • 综合性能&使用场景比较好
    • 时间复杂度:O(N*logN)
    • 空间复杂度:O(logN)
    • 稳定性：不稳定
  • [快速排序]优化方案
    • 三数取中法选key
      • 防止key都是极端数字 --> 递归过深 --> 栈溢出
    • 递归到小的子区间时，考虑使用插入排序
      • 大幅减少递归次数，提高效率
      • 例：最后一层递归占了总递归次数的50%，但可能只有极少量的数

2.归并排序

请添加图片描述

  • 基本思想：

  • 分治思维

    • 将已有序的子序列合并，得到完全有序的序列
    • 即先使每个子序列有序，再使子序列段间有序。
    • 若将两个有序表合并成一个有序表，称为二路归并

  • 归并排序核心步骤：
    请添加图片描述

  • 实现：

    //函数名前加_表示这个函数是内部函数，不对外提供接口 - 子函数
//后序思想
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
 
	int mid = (begin + end) / 2;
 
	//[begin, mid] [mid+1, end] 分治递归，让子区间有序
	_MergeSort(a,begin,mid,tmp);
	_MergeSort(a,mid+1,end,tmp);
 
	//归并 [begin, mid] [mid+1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)  //有一组结束则结束
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
 
	//已经有一组结束了，拷贝另一组剩余的
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
 
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
 
	//把归并数据拷贝回原数组
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
 
//时间复杂度:O(N*logN)
//空间复杂度:O(N)
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("MergeSort");
		exit(-1);
	}
 
	_MergeSort(a, 0, n - 1, tmp);
 
	free(tmp);
}

  • 非递归版本改写

  • 实现：

  • ①

    void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
 
	//手动归并
	int gap = 1;  //每次归并的元素个数
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i, i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
			//越界处理 - 修正边界
			if (end1 >= n)
			{
				end1 = n - 1;
				//[begin2, end2]修正为不存在区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				// [begin2, end2]修正为不存在区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
 
 
			//归并
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
 
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
 
		}
 
		//全部归并完后，拷贝回原数组
		memcpy(a, tmp, sizeof(int) * n);
 
		gap *= 2;
	}
 
	free(tmp);
}

  • ②

    void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
 
	//手动归并
	int gap = 1;  //每次归并的元素个数
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			//[i, i+gap-1] [i+gap,i+2*gap-1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
			//越界处理
			//end1越界或者begin2越界，则可以不归并了
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
 
			//归并
			int m = end2 - begin1 + 1;
			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
 
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
 
			memcpy(a + i, tmp + i, sizeof(int) * m);
		}
 
		gap *= 2;
	}
 
	free(tmp);
}

  • 特性总结：

    • 更多解决在磁盘中的外排序问题
    • 时间复杂度:O(N*logN)
    • 空间复杂度:O(N) – 缺点
    • 稳定性：稳定

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

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

相关文章

3389端口修改工具，3389端口修改工具的操作步骤

3389端口修改工具，3389端口修改工具的操作步骤

3389端口修改器&#xff1a; 这是一个专门用于修改3389端口的工具&#xff0c;可以方便地修改Windows远程桌面服务的端口号 使用注册表编辑器手动修改&#xff1a; 虽然这不是一个专门的工具&#xff0c;但Windows的注册表编辑器也可以用来修改3389端口。用户需要定位到特定的注…
阅读更多...
雷军-2022.8小米创业思考-10-高效率模型：便宜有好货；产品好，价格厚道，公司盈利；爆品模式，分摊成本；资金库存快速周转；铁人三项，硬件，新零售，互联网

雷军-2022.8小米创业思考-10-高效率模型：便宜有好货；产品好，价格厚道，公司盈利；爆品模式，分摊成本；资金库存快速周转；铁人三项，硬件，新零售，互联网

第十章 高效率模型 小米方法论 “铁人三项”的商业模式 完整的“小米模式”。这种模式有很多反直觉的地方&#xff0c;需要跟“便宜无好货”等很多固有观念做斗争。有些讽刺的是&#xff0c;小米模式天生就是为实现“便宜有好货”而奋斗。 效率是小米模式的基石&#xff0c…
阅读更多...
【CT】LeetCode手撕—5. 最长回文子串

【CT】LeetCode手撕—5. 最长回文子串

目录 题目1-思路2- 实现⭐5. 最长回文子串——题解思路 3- ACM实现 题目 原题连接&#xff1a;5. 最长回文子串 1-思路 子串的定义&#xff1a;子串是原始字符串的一个连续部分子序列的定义&#xff1a;子序列是原始字符串的一个子集记录最长回文子串的起始位置以及其长度&am…
阅读更多...
我的创作纪念日(1825天)

我的创作纪念日(1825天)

Ⅰ、机缘 1. 记得是大一、大二的时候就听学校的大牛说&#xff0c;可以通过写 CSDN 博客&#xff0c;来提升自己的代码和逻辑能力&#xff0c;虽然即将到了写作的第六个年头&#xff0c;但感觉这句话依旧受用; 2、今年一整年的创作都没有停止&#xff0c;本年度几乎是每周都来…
阅读更多...
Python基础教程（十七）：CGI编程

Python基础教程（十七）：CGI编程

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…
阅读更多...
轻兔推荐 —— Obsidian

轻兔推荐 —— Obsidian

via&#xff1a;轻兔推荐 - https://app.lighttools.net/ 简介 Obsidian 是一个强大的知识管理和笔记应用程序&#xff0c;它基于本地文件存储&#xff0c;支持Markdown格式&#xff0c;并提供丰富的插件生态系统。 - 通过双向链接和图谱视图&#xff0c;帮助用户发现笔记之间…
阅读更多...
联动联调，科学调度——探索智慧水务（中水）管理平台的无人值守新路径！

联动联调，科学调度——探索智慧水务（中水）管理平台的无人值守新路径！

项目背景 随着中国城市化的进程、城市规模以及对应的城市人口数量的增长&#xff0c;社会生产生活过程中产生的污水问题日益严重。如何实现污水再生、变废为宝显得尤为重要。 近年来&#xff0c;某市不断拓展与探索城市中水利用&#xff0c;让经无害化处理后的中水&#xff0…
阅读更多...
ubuntu gitlab 部署 私有git库

ubuntu gitlab 部署 私有git库

我的版本 ubuntu-22.04.2-live-server-amd64 GitLab 社区版 v17.0.1 注意剩余硬盘需要3GB以上 一、更新软件 sudo apt update二、gitLab 需要一些依赖项才能正常运行 sudo apt install -y curl openssh-server ca-certificates postfix1、出现邮件 选择 “Internet Site”并…
阅读更多...
华为wlan实验

华为wlan实验

分为三步&#xff1a;1、网络互通&#xff0c;2、AP上线&#xff0c;3、wlan业务 1、网络互通 crow-sw: vlan batch 20 100 dhcp enable int vlan 20 ip add 192.168.20.1 24 dhcp select interfaceinterface GigabitEthernet0/0/2port link-type accessport default vlan 100…
阅读更多...
Python | Leetcode Python题解之第150题逆波兰表达式求值

Python | Leetcode Python题解之第150题逆波兰表达式求值

题目&#xff1a; 题解&#xff1a; class Solution:def evalRPN(self, tokens: List[str]) -> int:op_to_binary_fn {"": add,"-": sub,"*": mul,"/": lambda x, y: int(x / y), # 需要注意 python 中负数除法的表现与题目不一…
阅读更多...
单链表经典算法题 1

单链表经典算法题 1

前言 学习了单链表&#xff0c;我们就做一些题来巩固一下。还有就是解题方法不唯一&#xff0c;我就只讲述为自己的方法。 目录 前言 1.移除链表元素 思路 代码 2.反转链表 思路 代码 3.链表的中间节点 思路 代码 总结 1.移除链表元素 思路 我们创建一个新的表…
阅读更多...
直播预约：存内计算加速大模型-未来智能计算的新引擎

直播预约：存内计算加速大模型-未来智能计算的新引擎

直播简介: 在人工智能飞速发展的今天&#xff0c;大模型的训练和推理对计算资源的需求日益增长。传统计算架构已逐渐难以满足其对速度和效率的极致追求。本次直播&#xff0c;我们将深入探讨如何利用存内计算技术&#xff0c;为大模型带来革命性的加速效果。 直播亮点: 技术…
阅读更多...
易趋（EasyTrack）资深咨询顾问刘苗受邀为第十三届中国PMO大会演讲嘉宾

易趋（EasyTrack）资深咨询顾问刘苗受邀为第十三届中国PMO大会演讲嘉宾

全国PMO专业人士年度盛会 易趋&#xff08;EasyTrack&#xff09;资深咨询顾问刘苗女士受邀为PMO评论主办的2024第十三届中国PMO大会演讲嘉宾&#xff0c;演讲议题为“企业级项目管理平台推动 IPD 数字化”。大会将于6月29-30日在北京举办&#xff0c;敬请关注&#xff01; 议…
阅读更多...
开源AGV调度系统OpenTCS中的路由器(router)详解

开源AGV调度系统OpenTCS中的路由器(router)详解

OpenTCS中的任务分派器router详解 1. 引言2. 路由器(router)2.1 代价计算函数&#xff08;Cost functions&#xff09;2.2 2.1 Routing groups2.1 默认的停车位置选择2.2 可选停车位置属性2.3 默认的充电位置选择2.4 即时运输订单分配 3. 默认任务分派器的配置项4. 参考资料与源…
阅读更多...
SpringBoot3 整合 Mybatis 完整版

SpringBoot3 整合 Mybatis 完整版

本文记录一下完整的 SpringBoot3 整合 Mybatis 的步骤。 只要按照本步骤来操作&#xff0c;整合完成后就可以正常使用。1. 添加数据库驱动依赖 以 MySQL 为例。 当不指定 依赖版本的时候&#xff0c;会 由 springboot 自动管理。 <dependency><groupId>com.mysql&l…
阅读更多...
C++ 33 之 const 修饰静态成员

C++ 33 之 const 修饰静态成员

#include <iostream> #include <string.h> using namespace std;// 定义静态const数据成员时&#xff0c;最好在类内部初始化,避免在类外重复初始化&#xff0c;也为了代码的可读性和可维护性class Students03{ public:// 两种写法都可以const static int s_a 10;…
阅读更多...
期末测试2（1）---PTA

期末测试2（1）---PTA

一开始写错了&#xff0c; 因为这个再定义一个和原函数一样类型的进行存储&#xff0c; 然后将第一个设置为最大的&#xff0c;依次用循环比较后面的&#xff0c; 最后输出 但是这个适用于找最大的、字符串这样最后只输出一个最大项比较好 对于结构体不好将比较的这个数所…
阅读更多...
Java9 后String 为什么使用byte[]而不是char?

Java9 后String 为什么使用byte[]而不是char?

之前认知里面&#xff0c;java的String一直是使用char数组&#xff0c;但是今天点进去瞟了一眼&#xff0c;发现不对。 源码如下&#xff1a; /*** The value is used for character storage.** implNote This field is trusted by the VM, and is a subject to* constant fold…
阅读更多...
boot项目配置邮箱发送

boot项目配置邮箱发送

最近项目准备进入测试阶段&#xff0c;时间相对充沛些&#xff0c;便对邮箱的信息发送记录下&#xff01; 邮箱设置-开启smtp协议及获取授权码 以QQ邮箱为例&#xff0c;其他邮箱大同小异&#xff01; 开启协议 获取授权码 具体代码 基于javax.mail实现 原文可看 前辈帖子…
阅读更多...
vscode 终端无法正常执行脚本命令如何解决

vscode 终端无法正常执行脚本命令如何解决

我们经常需要在vscode的中安装第三方依赖包&#xff0c;npm是前端目前最大的Node.js模块化管理系统&#xff0c;它能帮助开发者管理和发布Node.js模块。但很多时候我们在vscode的终端中执行npm install命令时经常会报以下错误&#xff1a; 但是在Windows的cmd命令提示符中执行n…
阅读更多...
最新文章

Copyright @ 2022~2023